二分、递归、搜索
题意:
给一个数组{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; }