题目分析
我们可以先从简单一点的情况开始分析，如果现在 \(a_{[i]},a_{[j]}\) 都不会进位，那么最后的 \(f(a_{[i]}+a_{[j]})=f(a_{[i]})+f(a_{[j]})\)。证明如下：
有两个数 \(x=\overline{x_nx_{n-1}....x_1}\) 和 \(y=\overline{y_my_{m-1}...y_1}\)。令 \(n\le m\)，由于不会进位,所以最后它们两相加应该是 \(z=\overline{y_my_{m-1}...y_{n+1}(x_n+y_n)...(x_1+y_1)}\)，那么 \(f(z)=y_m+y_{m-1}...y_{n+1}+x_n+y_n+....x_1+y_1=\sum\limits_{i=1}^n x_i+\sum\limits_{i=1}^m y_i=f(x)+f(y)\)。
考虑进位的情况，还是先从简单的入手，比如现在 \(x\) 和 \(y\) 都是一位数且它们的和要大于 \(10\)。那么 \(z=x+y=\overline{1(x+y-10)}\)，于是 \(f(z)=1+x+y-10=x+y-9=f(x)+f(y)-9\)。
根据之前的分析，我们可以推测一下，每进一次位最终的答案就会减去 \(9\)，那么 \(f(x+y)=f(x)+f(y)-9g(x+y)\)。其中 \(g\) 函数表示进位次数。
考虑如何求 \(g\) 函数，一个显然的结论：如果 \(x+y\) 会进位并且 \(z\ge y\)，那么 \(x+z\) 也必定进位。根据这个性质，我们可以存储所有数的后 \(i\) 位放进 \(nbr_{[i]}\) 中，从小到大排个序。接着双指针维护，一个指针指现在是求第 \(i\) 与多少个数发生进位，另一个指针指向现在第一个不能与 \(a_{[i]}\) 发生进位的数。前面这个指针从小往大扫，后面这个指针从大往小扫。
当然二分也是可行的，只是其他题解二分已经很详细了，但是双指针题解比较少，所以我来补充一发，顺便提供一下此题是如何一步一步思考到正解的。
最大时间复杂度大概是 \(O(n \log n)\)。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,a[N];
int sum[N][20];
vector<int>nbr[20];
int f(int cur,int x){
int ansi=0,cnt=0,now=1;
while(x){
cnt++;
ansi+=(x%10);
sum[cur][cnt]=sum[cur][cnt-1]+(x%10)*now;
now*=10;
x/=10;
}
return ansi;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n;
int ansi=0;//所有f函数的和
for(int i=1;i<=n;i++){
cin>>a[i];
ansi+=f(i,a[i]);
for(int j=1;j<=15;j++){
if(!sum[i][j]) sum[i][j]=sum[i][j-1];//有可能这个数不满15位
nbr[j].push_back(sum[i][j]);
}
}
for(int i=1;i<=15;i++){
nbr[i].push_back(0);
sort(nbr[i].begin(),nbr[i].end());
}
int tmp=0,k=1;//tmp表示所有g函数的和
for(int i=1;i<=15;i++){
int now=n;
k*=10;
for(int j=0;j<=n;j++){
while(nbr[i][j]+nbr[i][now]>=k) now--;
tmp+=n-now;
}
}
cout<<ansi*2*n-tmp*9;
return 0;
}
感谢巨佬 Biuld 帮我 debug 并教我怎么算时间复杂度/bx