解决思路
寻求减到 0 所需的最小次数，即 \(Num(n) \Rightarrow Num(n-x)+1\)
当存在一个 x 使得 （n - x）% 10 = 0 时，那么（n - x）到下一次个位为 0 时至少需要两次，即该过程至少需要 3 次
如果存在一个 x' > x，那么上述过程可以简化到至少需要 2 次
一般情况下，当 n 中的前面一段（百位之前）的数比较小时，每次减法运算都会使得个位出现较大的数，此时 x' 大小不影响次数
对于 n(个位数为 0) -> 0 可以看作 n(个位数为 0) -> n'(个位数为 0) -> 0，因此每次减去 max(x') 所需次数 ≤ 任意的 x'所需次数
#include <bits/stdc++.h>
int getMaxDigit(long long n) {
long long d = 0;
while (n > 0) {
d = std::max(d, n % 10);
n /= 10;
}
return int(d);
}
int main() {
long long n; std::cin >> n;
int count = 0;
while (n > 0) {
int d = getMaxDigit(n);
n -= d;
++count;
}
std::cout << count << std::endl;
return 0;
}
缺陷
该做法无法通过 C2