自动搬运

查看原文

来自洛谷，原作者为

	Zaku Кто не идет вперед, тот идет назад: стоячего положения нет.

搬运于2025-08-24 22:41:39，当前版本为作者最后更新于2023-02-26 23:07:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题考双指针和排序。

解法：

从数组里面选取两个数字，进行拼接，暴力枚举时间复杂度为 $\Theta(n^2)$，会超时。

我们可以使用类二分的双指针算法，先将数组进行排序，左指针指向数组开始点，右指针指向数组结束点，向中间移动。对于两个指针选取到的数，进行拼接。

• 如果拼接后的数字小于 $k$，那么因为 $r$ 指针指向的是目前的最大值，所以 $[l,r]$ 区间内的所有数字与 $l$ 拼接的结果都小于 $k$，所以答案加上 r - l，并且更新左指针 l ++；

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

• 如果拼接后的数字大于 $k$，不更新答案，更新右指针 r –- 即可。

由于交换 $A_i$ 和 $A_j$ 的顺序总是被视为 $2$ 种拼法，所以我们跑两遍双指针，分别放前面、放后面即可。

对于拼接操作，如果直接使用数字进行拼接比较麻烦，可以用 to_string 转化为字符串再进行拼接，但需要自己手写一个字符串比较大小的函数。

代码：

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
ll a[N];
string s[N], str;//s[i]表示转为字符串的 a[i];str表示转为字符串的 k 
ll n, k;
int cmp(string s1, string s2) {//字符串大小比较，不解释 
    if (s1.size() == s2.size()) { 
        if (s1 == s2) return 0;
        else if (s1 < s2) return 1;
        else return -1;
    }
    if (s1.size() < s2.size()) return 1;
    else return -1;
}
void init() {//初始化，不解释 
	cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i ++ ) s[i] = to_string(a[i]);
    str = to_string(k);
}
int main() {
	init();
    ll res = 0;
    //第一遍双指针 
    int l = 1, r = n;
    while(l <= r) {
        int t = cmp(s[l] + s[r], str);
        //l放前面，r放后面 
        if(t == 1) {//拼接后小于k 
            res += r - l;
            l ++;
        } else if(t == 0) {//拼接后等于k 
            res += r - l;
            l ++, r --;
        } else r --;//拼接后大于k 
    }
    //第二遍双指针 
    l = 1, r = n;
    while(l <= r) {
        int t = cmp(s[r] + s[l], str);//r放前面l放后面 
        if(t == 1) {//同第一遍
            res += r - l;
            l ++;
        } else if(t == 0) {
            res += r - l;
            l ++, r --;
        } else r --;  
    }
    cout << res;
    return 0;
}

个人马蜂有变化，不喜勿喷