二分、递归、搜索

题意：
给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，
求 h(ai,aj) 的和，对于所有i<j，0的位数为1

拿到这一题，第一反应就是整体二分。想将大问题分解成为小问题，在合并进行求解。
输入数据存储在数组a中，定义一个函数 long long solve(int l,int r)
表明求解数组a+l,a+r范围内的h(a,b)和。（左闭右开）
那么我们对于数组a，长度为n.
令mid = n/2 ，先求出solve(0,mid)在求出solve(mid,n)
那么答案就是ans = solve(0,mid)+solve(mid,n)+h(ai,aj)之和（0<=i<mid,n>j>=mid）
递归的终点是r-l==1这时候只有一个元素自然返回0

那么问题的关键来了：

• 如何求解h(ai,bi)之和(l<=i<mid,mid<=j<r)呢
  我们想对于ai假设其为一位数，那么他想加上一个aj升位变成二位数至少要加上10-ai才可以！！
  这是否给我们一点启发。我们可以把这个问题转化为搜索问题。对a+mid到a+r排个序，然后在a+mid到a+r
  之间使二分搜索lower_bound，查找10-ai，那么能够使得ai升上两位及两位为以上aj数目为
  a+r-lower_bound(a+mid,a+r,10-ai);同理对于100,1000,10000,一直到1e9也是一样的！！
  （因为数据最大是1e8所以这里可能升高的最大位数是1e9）
  把这些数放进一个数组中b[] = {10，100，1000，10000，100000，1000000，10000000，100000000，1000000000}；
  那么对于一个ai我们只需二分搜索(b[k]-ai)9次即可（如果b[k]-ai<=0则不搜索）
  如此我们实现了两个小问题的合并！！！
  时间复杂度为O(n(logn)^2)还行吧。
  下面是代码，注意细节。

#include<iostream>;
#include<algorithm>;
using namespace std;
typedef long long ll;
const int max_n = 1e5 + 100;
int a[max_n];
ll b[] = { 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) / 2;
    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() {
    ios::sync_with_stdio(0);
    int n;cin >> n;
    for (int i = 1;i <= n;i++)cin >> a[i];
    cout << solve(1, n + 1) << endl;
}