D. Decrease the Sum of Digits - 题解

比赛与标签

比赛: Codeforces Round 667 (Div. 3) 标签: greedy, math 难度: *1500

题目大意喵~

主人，这道题是这样的呐：

我们有一个正整数 n 和一个目标值 s。我们可以对 n 进行一种操作：把它加一 (n = n + 1)。我们的任务是，找到最少需要多少次操作，才能让 n 的各位数字之和小于或等于 s。

简单来说，就是要我们找一个最小的 x >= 0，使得 (n + x) 的各位数字之和 sum_digits(n + x) <= s。我们要输出的就是这个最小的 x 啦！

解题思路大揭秘！

嘿嘿，一看到要“最小化”操作次数，我们聪明的直觉就会想到贪心或者动态规划，对不对？这道题呀，用一个巧妙的贪心思路就能解决啦！

首先我们想一下，怎样才能通过增加一个数来减小它的各位数字之和呢？答案就是——进位！喵~

举个栗子：n = 49，它的各位数字之和是 4 + 9 = 13。我们给它 +1，它就变成了 50，各位数字之和变成了 5 + 0 = 5。哇，一下子就变小了好多！

这个例子告诉我们，要想让各位数字之和变得更小，最有效的方法就是让数字的末尾出现尽可能多的 0。因为 0 对数字和的贡献是最小的嘛！

那么，我们的目标就变成了：找到一个最小的数 n' >= n，它不仅要满足 sum_digits(n') <= s，而且为了让 n' 尽可能小（从而让操作次数 n' - n 最小），n' 的形式最好是后面带着一串 0 的。

什么样的数后面会带着一串 0 呢？当然是 10 的倍数、100 的倍数、1000 的倍数…… 啦！

所以，我们的贪心策略就来啦：

首先，检查一下当前的 n 是不是已经满足 sum_digits(n) <= s。如果满足，那太棒了，我们一步都不用动，答案就是 0！
如果不满足，我们就尝试把 n 变成一个末尾至少有一个 0 的数。要怎么变呢？当然是把它变成大于等于 n 的、最小的 10 的倍数。我们计算出这个新的数 n'，然后看看它的各位数字之和是否满足条件。
如果还不满足，我们就再贪心一点！尝试把 n 变成一个末尾至少有两个 0 的数，也就是大于等于 n 的、最小的 100 的倍数。再检查它的各位数字之和。
我们就这样一直试下去：1000 的倍数、10000 的倍数……直到我们找到第一个满足条件的 n'。

因为我们是按 10、100、1000…… 的顺序来寻找目标 n' 的，这保证了我们找到的第一个满足条件的 n' 一定是所有可能的目标数中最小的那个。所以，它对应的操作次数 n' - n 也一定是最小的！

举个例子: n = 500, s = 4

sum_digits(500) = 5，大于 4。
我们尝试让 n 变成下一个 10 的倍数。500 本身就是 10 的倍数，所以 n' 还是 500，不满足。
尝试让 n 变成下一个 100 的倍数。500 本身就是 100 的倍数，n' 还是 500，不满足。
尝试让 n 变成下一个 1000 的倍数。大于等于 500 的最小的 1000 的倍数是 1000。
- n' = 1000。
- sum_digits(1000) = 1，小于 4！满足条件了！
- 需要的操作次数就是 1000 - 500 = 500。这就是答案啦！

一个重要的小细节喵：题目中的 n 最大可以到 10^18，这刚好在 long long 的范围内。但是，我们把它变成下一个 10^k 的倍数时，结果可能会超过 long long 的最大值（比如 n 是 99...9）。所以，为了安全起见，我们在计算新的 n' 和操作次数时，要用范围更大的 __int128_t 类型哦！

代码实现时间~

下面就是把我们的思路变成代码的时刻啦！我已经加上了详细的注释，主人可以轻松看懂的~

cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

// 这是一个计算 long long 类型数字各位和的辅助函数喵~
// 用取模和除法通常比转成字符串更快哦。
long long get_sum_ll(long long n) {
    long long sum = 0;
    long long temp = n;
    while (temp > 0) {
        sum += temp % 10;
        temp /= 10;
    }
    return sum;
}

// 这是一个计算 __int128_t 类型数字各位和的辅助函数。
// 各位数字的和肯定不会超过 long long 的范围。
long long get_sum_128(__int128_t n) {
    long long sum = 0;
    __int128_t temp = n;
    while (temp > 0) {
        sum += temp % 10;
        temp /= 10;
    }
    return sum;
}

// 因为 std::cout 不直接支持 __int128_t，所以我们需要自己写一个打印函数~
void print_128(__int128_t n) {
    if (n == 0) {
        std::cout << "0";
        return;
    }
    std::string s = "";
    __int128_t temp = n;
    while (temp > 0) {
        s += (char)((temp % 10) + '0');
        temp /= 10;
    }
    std::reverse(s.begin(), s.end());
    std::cout << s;
}

void solve() {
    long long n;
    int s;
    std::cin >> n >> s;

    // 第一步：检查初始的 n 是否已经满足条件。
    if (get_sum_ll(n) <= s) {
        std::cout << 0 << "\n";
        return;
    }

    // 我们的核心思路：找到最小的 n' >= n，使得 sum_digits(n') <= s。
    // 最有效降低各位数字和的方法就是通过进位产生很多0。
    // 所以我们依次尝试将 n 变为 10, 100, 1000... 的倍数。
    // 因为我们是按从小到大的顺序检查这些候选目标的，所以第一个满足条件的就对应了最小的操作数。

    // 为了防止 n + moves 溢出 long long，我们使用 __int128_t。
    // p 是我们检查的基数，从 10^1, 10^2, ... 一直到 10^19。
    __int128_t p = 1;
    for (int i = 0; i < 19; ++i) {
        p *= 10;
        
        __int128_t n_128 = n;
        // 计算需要多少步才能到达 p 的下一个倍数。
        // 这个公式 (p - (n % p)) % p 非常巧妙，喵~
        // 1. 如果 n 已经是 p 的倍数, n % p = 0, moves = (p - 0) % p = 0。
        // 2. 如果不是, moves = p - (n % p)。
        __int128_t moves = (p - (n_128 % p)) % p;
        
        // 这就是我们操作之后的新数字 n'
        __int128_t n_new = n_128 + moves;

        // 检查新数字的各位和是否满足条件。
        if (get_sum_128(n_new) <= s) {
            print_128(moves);
            std::cout << "\n";
            return; // 找到答案，就可以结束啦！
        }
    }
}

int main() {
    // 这两行是为了让输入输出快一点，是竞赛中的好习惯哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(log n) 的说。这里的 n 是指输入的数字大小。对于每个测试用例，我们有一个循环，它最多迭代 19 次（因为 n 最大是 10^18，我们最多考虑到 10^19）。在循环内部，我们进行的是一些大数的基本算术运算和求各位数字之和。求和操作的复杂度与数字的位数成正比，也就是 O(log n)。所以总的时间复杂度是 O(19 * log n)，我们通常简化为 O(log n)。非常快呢！
空间复杂度: O(1) 的说。我们只用了几个变量来存储 n, s, p 等，没有使用额外的、随输入规模变大的数据结构。所以空间是恒定的，非常节省~

知识点小总结喵！

这道题虽然看起来有点复杂，但核心思想其实很直接，它教会了我们这些东西呐：

贪心思想: 面对一个问题，尝试寻找一个局部最优解（比如，先尝试让末尾变成一个0，再尝试两个0...），并证明这个局部最优可以导向全局最优。这是解决很多优化问题的强大武器！
数感与性质: 理解数字运算的性质，比如加法如何通过进位影响各位数字之和，是解题的关键洞察力。
大数处理: 在处理像 10^18 这样的大数时，要时刻警惕运算过程中可能发生的溢出。在 C++ 中，__int128_t 是我们的好朋友！
模块化代码: 把计算各位数字之和、打印大数等功能封装成独立的函数，会让主逻辑更清晰，代码也更易读和维护哦！

好啦，这道题的讲解就到这里啦！主人是不是感觉豁然开朗了呢？只要抓住“进位”和“造零”这个核心，问题就迎刃而解了。继续加油，下一道题也一定没问题的，喵~！

D. Decrease the Sum of Digits - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现时间~ ​

复杂度分析的说 ​

知识点小总结喵！ ​