又浪费一道好题
我首先想的是，\(x\) 显然最优取某些 \(a_i\) 往前进位时的值。然后就误以为 \(x\) 的取值是 \(O(n \log_{10} V)\) 的了……
既然没发现什么性质，那就直接 dp 吧！设 \(f_{d, i}\) 为从低到高前 \(d\) 位，所有 \(a_i\) 进位之和为 \(i\)。然后可以发现，把所有 \(a_i\) 按照 \(a_i \bmod 10^d\) 从大到小排序，在这一位进位的只可能是前面几个值。做完了？
code
// Problem: D - Sum of Sum of Digits
// Contest: AtCoder - AtCoder Regular Contest 153
// URL: https://atcoder.jp/contests/arc153/tasks/arc153_d
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, a[maxn], pw[12], f[12][maxn];
void solve() {
scanf("%d", &n);
pw[1] = 1;
for (int i = 2; i < 12; ++i) {
pw[i] = pw[i - 1] * 10;
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
mems(f, 0x3f);
f[0][0] = 0;
for (int d = 1; d <= 10; ++d) {
sort(a + 1, a + n + 1, [&](int x, int y) {
return x % pw[d] > y % pw[d];
});
for (int k = 0; k <= 9; ++k) {
int c = 0, s = 0;
for (int i = 1; i <= n; ++i) {
c += (((a[i] / pw[d]) % 10 + k) >= 10);
s += ((a[i] / pw[d]) % 10 + k) % 10;
}
f[d][c] = min(f[d][c], f[d - 1][0] + s);
for (int i = 1; i <= n; ++i) {
if ((a[i] / pw[d]) % 10 + k == 9) {
++c;
s -= 9;
} else {
++s;
}
f[d][c] = min(f[d][c], f[d - 1][i] + s);
}
}
}
int ans = 2e9;
for (int i = 0; i <= n; ++i) {
ans = min(ans, f[10][i] + i);
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}