P8708 [蓝桥杯 2020 省 A1] 整数小拼接 题解

Zaku · 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;
}

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