位数差

思路：
1.拿到题的第一个思路就是暴力，直接两层循环，复杂度在以上，结合数据范围，是一定会超时的。
2.接着可以考虑整体二分。想将大问题分解成为小问题，在合并进行求解。
3.将的问题化为的问题。
4.可以定义一个函数，表示求之间的答案。

ll solve(int l,int r) {
    ;
}

5.[0,n)可以求到[0,mid),[mid,n)之间的答案，那么最终的答案就还要加上与的位数差

ll ans=solve(l,mid)+solve(mid,r);
sort(a+mid,a+r);
for(int i=l;i<mid;++i)
for(int j=0;j<9;++j) if(b[j]-a[i]>0)//b[j]>a[i]
   ans+=a+r-lower_bound(a+mid,a+r,b[j]-a[i]);//a[k]+a[i]>=b[j],k>=mid

Code：

#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int a[maxn];
int b[9]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
ll solve(int l,int r) {
    if(r-l==1) return 0;
    int mid=l+r>>1;
    ll ans=solve(l,mid)+solve(mid,r);
    sort(a+mid,a+r);
    for(int i=l;i<mid;++i)
    for(int j=0;j<9;++j) if(b[j]-a[i]>0)
        ans+=a+r-lower_bound(a+mid,a+r,b[j]-a[i]);
    return ans;
}
int main() {
    js; int n;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    cout<<solve(1,n+1)<<endl;
}