二分、递归、搜索

题意:
给一个数组{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;
}