位数差（整体二分、分治）
链接：https://ac.nowcoder.com/acm/problem/14380
来源：牛客网
题目描述
，0的位数为1。输入描述:
第一行读入一个正整数 n (1 <= n <= 105)。
第二行读入 n 个非负整数，第 i 个表示a[i] (0 <= a[i] <= 108)。
输出描述:
一行表示答案。
输入
10 0 1 2 3 4 5 6 7 8 9
输出
20
我们可以考虑整体二分(分治)，将大问题分解成为小问题。二分区间长度，将L~R的问题化为L~mid、mid+1~R的问题，分治每个区间的数位差贡献，再合并进行求解。合并计算时，对于当前左右区间，还要加上a[i]在左边，a[k]在右边的情况。具体可以对右区间进行排序，遍历左区间的ai进行求在右区间符合条件的aj个数即可。
感觉这种区间题目好像都可以用分治去思考解法。对于给出的区间，直接二重for枚举很显然会TLE掉，那么我们看能不能去降降时间复杂度，假设[1, n]这个区间我们存在一个分治函数，可以先分开递归求[1, mid]，[mid+1, n]区间的答案，那么最终的答案就还要加上a[i]在左区间，a[j]在右区间的情况即可。因为我们只用去右边匹配存在进位的个数即可，这样就可以对右边元素排序，直接二分查找就可了。
因为关系到一个要进位，我们想对于ai假设其为一位数，那么他想加上一个aj变成两位数至少要加上10-ai才可以。这启发我们可以把这个问题转化为搜索问题。对mid+1到R排个序，然后在mid+1到R之间使二分搜索lower_bound()，查找10-ai，那么能够使得ai升上两位及两位为以上aj数目即为对ans的贡献。同理对于100,1000,10000,一直到1e9也是一样的。
1 #include <bits/stdc++.h> 2 typedef long long LL; 3 #define pb push_back 4 #define mst(a) memset(a,0,sizeof(a)) 5 const int INF = 0x3f3f3f3f; 6 const double eps = 1e-8; 7 const int mod = 1e9+7; 8 const int maxn = 1e5+10; 9 using namespace std; 10 11 int a[maxn]; 12 LL jz[]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; 13 14 LL solve(int L,int R) 15 { 16 if(L==R) return 0; 17 int mid = (L+R)/2; 18 LL res = solve(L,mid) + solve(mid+1,R); //分治 19 sort(a+mid+1, a+R+1, less<int>()); 20 for(int i=L;i<=mid;i++) // 问题合并 21 { 22 for(int j=0;j<9;j++) 23 { 24 if(jz[j] > a[i]) //注意没有= 25 res += a+R+1 - lower_bound(a+mid+1,a+R+1,jz[j]-a[i]);//加上满足的个数 26 } 27 } 28 return res; 29 } 30 31 int main() 32 { 33 #ifdef DEBUG 34 freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout); 35 #endif 36 37 int n; 38 scanf("%d",&n); 39 for(int i=1;i<=n;i++) 40 scanf("%d",&a[i]); 41 printf("%lldn",solve(1,n)); 42 return 0; 43 }
-
原文链接: https://www.cnblogs.com/jiamian/p/13234234.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/362289
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
