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

· · 题解

前言

传送门

blog

思路

这种选出两个数拼接在一起的题，一看就可以使用 two-point，我们使用 l 和 r 分别从最大的和最小的开始搜索，进行两次。

  1. 以 l 为头，r 为尾。

  2. 以 r 为头，l 为尾。

如何比较大小呢？我们可以先去做宇宙总统这道题。

首先排序的 cmp：

bool cmp(string x,string y){
    if(x.size() != y.size())return x.size() < y.size();
    else return x < y; 
}

然后是比较拼接的数的大小的 check：

int check(string x,string y){
    if(x == y)return -1;
    else return cmp(x,y);
}

这样我们就可以完成排序与比大小了。

AC Code

#include <bits/stdc++.h>
using namespace std;

string a[100010];

bool cmp(string x,string y){
    if(x.size() != y.size())return x.size() < y.size();
    else return x < y; 
}

int check(string x,string y){
    if(x == y)return -1;
    else return cmp(x,y);
}

int main(){
    int n;
    string k;
    cin>>n>>k;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
    }
    sort(a + 1,a + 1 + n,cmp);
    int l = 1,r = n;int ans = 0;
    while(l < r){
        int ch = check(a[r] + a[l],k);
        if(ch == -1){
            ans += r - l;
            l++,r--;
        }else
            if(ch == 1){
                ans += r - l;
                l++;
            }else{
                r--;
            }
    }
    l = 1,r = n;
    while(l < r){
        int ch = check(a[l] + a[r],k);
        if(ch == -1){
            ans += r - l;
            l++,r--;
        }else
            if(ch == 1){
                ans += r - l;
                l++;
            }else{
                r--;
            }
    }
    cout<<ans;
}