Voldemort's blog

Voldemort's blog

我好菜啊

题解 AT3867 【[AGC021A] Digit Sum 2】

posted on 2020-08-27 14:05:05 | under 题解 |

题解 AT3867 【[AGC021A] Digit Sum 2】
由于 AtCoder 的端口 SPFA 了,所以本题解的代码是直接在原 OJ 上提交的,AC记录如下:

Solution

这道题目第一眼觉得是 $\Theta(N)$ 的爆搜,然后一看数据范围……
于是开始想数学方法。
我们可以发现,对于任意的一个数 $n$ ,只有两个数可能成为我们想要的答案,第一个是 $n$ 自己,第二个是形如 $a999999\dots999$ 的形式,所以我们把这两个数字的各数位数字之和算出来,比较即可。

Code

#include <bits/stdc++.h>
using namespace std;

int ans1,ans2;  //ans1表示n自己,ans2表示第二种情况

string S;

int main() {
    cin >> S;
    int len = S.size();
    for(int i = 0;i < len;i++) {
        ans1 += S[i] - '0';
        if(i == 0) {    //首位需要少一,不然就比n大了
            ans2 += (S[i] - '0' - 1);
            continue;
        }
        ans2 += 9;  //其他位都是9
    }
    printf("%d\n",max(ans1,ans2));
    return 0;
}