THC

WIKI

0%

ARC153D Sum of Sum of Digits

Posted on Edited on

简要题意

给定长度为 \(n\le2\times10^5\) 的序列 \(1\le A_i<10^9\) ，定义 \(f(x)\) 为 \(x\) 的数位和如 \(f(153)=9\) ，求 \(\min\limits_{x\ge 0}\sum\limits_{i=1}^nf(A_i+x)\) 。

题解

在英语课上手玩了一下这题，先不考虑 \(+x\) 先考虑 \(+1\) ，那么我们发现对于某个数 \(a\) ， \(f(a+1)=f(a)+1-9\cdot\#进位\) 如 \(f(99+1)=f(99)+1-9*2=1\) 。

于是有一个自然想法把 \(f(A_i+x)\) 拆成 \(f(A_i)+x-9\cdot\#进位\) ，就是把 \(x\) 拆成 \(x\) 个 \(+1\) ，总过程中有几个进位，那么对于给定 \(x\) 答案就是 \(\sum f(A_i)+nx-9\sum\#进位_i\) 。

然后显然这个进位是具有周期的，例如连续 \(9\) 个 \(0\) 之类的，可以化为一个比较好的形式，考虑把进位拆开，就是 \(\#进位_i=\sum\limits_k\lfloor\dfrac{x-(10^k-A_i\%10^k)}{10^k}\rfloor\) ，然后显然 \(10^k-A_i\%10^k\) 这个东西是确定的，且能排出一个大小，当时想着就是依据大小来搞 \(dp\) 类似物，但是下课了，也就去恰饭了。

后来看了看题解感觉总的过程差不多，不过初始的考虑不太一样，题解就是按位确定 \(x\) ，考虑 \(F(Array)\) 表示对于给定 \(Array\) 的答案， \(F_r(Array)\) 表示最低位为 \(r\) 的时候的答案，如 \(F_1(\{123,45,678,90\})=20+F(\{12,4,67,9\})\) ，然后显然 \(F(Array)=\min\limits_rF_r(Array)\) 那么这样子就能把问题转化为一个子问题。

然后我们需要考虑进位问题，进位也是有规律的，根据 \(A_i\%10^k\) 的大小从大到小依次进位，不会出现小的进了大的没进这种情况，就可以设计 \(dp\) 状态 \(f_{k,n}\) 表示考虑 \(\{A_i/10^k\}\) 且有 \(n\) 位进位时的答案，那么终态就是 \(f_{0,0}\) ，初态为 \(f_{\infty,i}=i\) ，转移的时候存一下几个进位了就好，然后写得优雅一点就好了。 \(O(nk\log n)\) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int N = 200100;
int n, a[N], f[11][N];
vi id[11];
signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int k = 9, pw = 1e9; k >= 0; k--, pw /= 10) {
        for(int i = 1; i <= n; i++)
            id[k].pb(i);
        sort(id[k].begin(), id[k].end(), [&](const int i, const int j) {
            return a[i] % pw > a[j] % pw;
        });
    }
    memset(f, 0x3f, sizeof(f));
    for(int i = 0; i <= n; i++) f[10][i] = i;
    for(int k = 9, pw = 1e9; k >= 0; k--, pw /= 10) {
        for(int r = 0; r <= 9; r++) {
            int val = 0, cnt = 0;
            for(int i = 1; i <= n; i++) {
                val += ((a[i] / pw) + r) % 10;
                if((a[i] / pw) % 10 + r >= 10)
                    cnt++;
            }
            f[k][0] = min(f[k][0], val + f[k + 1][cnt]);
            for(int i = 1; i <= n; i++) {
                int i_ = id[k][i - 1];

                val -= ((a[i_] / pw) + r) % 10;
                if((a[i_] / pw) % 10 + r >= 10)
                    cnt--;
                val += ((a[i_] / pw) + r + 1) % 10;
                if((a[i_] / pw) % 10 + r + 1 >= 10)
                    cnt++;

                f[k][i] = min(f[k][i], val + f[k + 1][cnt]);
            }
        }
    }
    printf("%d\n", f[0][0]);
    return 0;
}