1 条题解

  • 1
    @ 2024-3-8 15:27:21

    从数组里面选取两个数字,进行拼接,暴力枚举时间复杂度为 O(n2)O(n^2),会超时。 \\我们可以使用双指针算法,先将数组进行排序,左指针指向数组开始点,右指针指向数组结束点,向中间移动。对于两个指针选取到的数,进行拼接。 \\如果拼接后的数字小于 k,那么因为 rr 指针指向的是目前的最大值,所以 [l,r][l,r] 区间内的所有数字与 ll 拼接的结果都小于 kk,所以答案加上 rlr - l,并且更新左指针l++ l ++

    \\如果拼接后的数字等于 k,同理答案加上 r - l,但是此时需要同时更新左、右指针 l++l ++, rr --

    \\如果拼接后的数字大于 k,不更新答案,更新右指针 rr -- 即可。

    \\由于交换 a[i]和a[j]的顺序总是被视为 2 种拼法,所以我们跑两遍双指针,分别放前面、放后面即可。

    参考代码
    
    #include<bits/stdc++.h>
    using namespace std;
    int n, ans;
    long long k, a[100010];
    long long pj(int i, int j) //整数i与整数j拼接
    {
        long long tj = j, sj = 1;
        while (tj > 0)
        {
            sj *= 10;    //算出整数j的位数
            tj /= 10;
        }
        return i * sj + j;
    }
    int main()
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1); //将数组从小到大排列
        int i = 1, j = n;
        while (i != j)
        {
            long long t = pj(a[i], a[j]);
            if (t <= k)
            {
                ans += j - i;    //如果小于等于k,那么统计答案
                i++;
            }
            else j--; //否则移动j指针,缩小范围
        }
        //反着再拼一遍
        i = 1;
        j = n;
        while (i != j)
        {
            long long t = pj(a[j], a[i]);
            if (t <= k)
            {
                ans += j - i;
                i++;
            }
            else j--;
        }
        cout << ans;
        return 0;
    }
    
    • 1

    信息

    ID
    690
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    (无)
    递交数
    54
    已通过
    37
    上传者