[AGC025A] Digits Sum 题解

· · 题解

读完题目，我们可以先从举特例开始寻找解题方法。

比如有一个数 212303，想要分解它，并且保证分解成的两个数每位上的数之和最小，我们就可以想到：如何让一个数尽量大，同时使得每位数之和最小？

很显然，将一个数乘 10，数直接变成原来的 10 倍，而每位数之和不变！还是从刚才的 212303 开始分解，由刚才的推导可知，分解后若其中一个数是 200000（用最少的每位数之和来凑成最大的数），那么可以证明，这是最优方案。易得最终答案就为此正整数的位数之和。

但是有一种特殊情况：分解 10 的非负整数次幂。例如 1000，按上面所说的方法分解，只能分解成一个数，就是它本身。这个时候我们再用上面推出的规律，就很容易地得出：分解成 500 和 500、400 和 600……是最佳方案（最大限度地乘 10）。最终答案为 10。

那么有的同学就要问了：那么像 600、9000 这样由一个小于 10 且大于 1 的整数乘以 10 的若干次幂的该如何分解呢？仍然举例：分解 600，将它分解成 300 和 300、200 和 400……你发现了吗？答案依然与第一种情况相同。

所以，假设 f(x) 的值是正整数 x 的每位上的数之和，g(x) 是分解后最大的答案，那么 g(x) 满足以下的条件：

g(x)=\begin{cases}f(x)&{f(x)\ne 1}\\10&{f(x)=1}\end{cases}

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  string s; cin>>s; int c=0; // 用 string 来读入
  for(char i:s)c+=i-48; // 求每位上的数的和 
  cout<<(c==1?10:c)<<endl; // 分类讨论
  return 0;
}