【每日一题】Problem 331C1. The Great Julya Calendar

原题

解决思路

寻求减到 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