ACM - 位数差 - 分治二分

题目链接

官方题解

题意：
中文题，自己看

样例解释：
10个数
0 ~ 9
其中，1有9，2有8，9，以此类推，答案是1+2+3+4+4+3+2+1=20

思路分析：
（1）为啥不能直接排序？再二分。
举个例子。
6
60 70 80 90 100 110
6
110 100 90 80 70 60
这两组数据，按照题意，是不同的两组数据。拿（60，110）举例。
在第一组，60和110，贡献1
在第二组，110和60，贡献0
所以，不能直接排序。
注意：1<=i<j<=n.所以i，j的选取是讲顺序的

（2）为啥需要分治？
这个简单。因为平方的算法超时。但是分治之后就降级成了nlogn的算法。

（3）细节。
样例中。1和9，变成的是1和10，位数差是1。
根据数据范围，得考虑的是，10，100，1000......等10的次幂的情况。
比如，4得考虑6，96，996以上（包括）等情况。
得用 lower_bound()函数。

（4）std使用。
这里需要用到 lower_bound()。也记录一下 upper_bound()
学习一下std姿势吧

上代码

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

const int maxn = 1e5 + 20;
int a[maxn];
int ten[10] = {10};
int n;

typedef long long ll;
ll calc(int l, int r){
    if (l == r) return 0;
    int mid = (l + r) >> 1;
    #ll ans = calc(l, mid) + calc(mid + 1, r);
    ll ans = 0;
    ll ans1 = calc(l, mid);
    ll ans2 = calc(mid + 1, r);
    sort(a + mid + 1, a + r + 1);
    for(int i = l; i <= mid; i++)
        for(int j = 0; j <= 8; j++)
            if (ten[j] > a[i])
                ans += a + r + 1 - lower_bound(a + mid + 1, a + r + 1, ten[j] - a[i]);
    return ans + ans1 + ans2; 
}

int main(){
    //freopen("input.txt", "r", stdin);
    for(int i = 1; i <= 8; i++)
        ten[i] = ten[i - 1] * 10;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    //sort(a + 1, a + n + 1);
    printf("%lld\n", calc(1, n));
    return 0;
}