D. Zero Remainder Array - 题解

比赛与标签

比赛: Codeforces Round 653 (Div. 3) 标签: math, sortings, two pointers, *1400 难度: *1400

喵喵，这是什么任务呀？ - 题目大意

主人，这个任务是这样的呐：

我们有一个包含 n 个正整数的数组 a，还有一个整数 k。一开始，我们还有一个计数器 x，它的初始值是 0。

我们有两种操作：

1. 操作并升级：选择数组中的一个元素 a_i，把它变成 a_i + x。然后，让 x 的值加 1。这个操作对每个位置 i 最多只能用一次哦！
2. 只升级：什么也不对数组做，只是让 x 的值加 1。

我们的目标是，通过一系列操作，让数组 a 里的所有元素都能被 k 整除。我们需要找到达成这个目标所需要的最少总操作次数，喵~

输入：会给我们 t 组测试数据。每组数据包含 n 和 k，以及数组 a 的 n 个元素。 输出：对于每组数据，输出一个数字，表示最少的操作次数。

本猫娘的思考时间！ - 解题思路

嘿嘿，这个问题看起来有点复杂，但只要我们理清思路，就会发现它其实是一只温顺的小猫咪~

首先，最关键的一点是：总操作次数完全取决于我们使用的最大的 x 值。为什么呢？因为 x 从 0 开始，每次操作（不管是哪种）都会让 x 加 1。如果我们使用的最大的 x 是 max_x，那就意味着我们总共进行了 max_x 次 x 的自增，再加上 x=0 时的初始状态，总共就是 max_x + 1 步（或者说 max_x + 1 个时间点）。所以，问题就变成了：如何用最小的 max_x 来完成任务？

好，接下来我们考虑如何让一个元素 a_i 被 k 整除。我们需要在某个 x 的时刻，执行 a_i := a_i + x，使得 (a_i + x) % k == 0。

如果 a_i 本身就能被 k 整除（也就是 a_i % k == 0），那真是太棒了！我们根本不需要对它进行任何操作，可以直接忽略它，喵~

如果 a_i % k != 0，设 a_i % k = r。为了让 a_i + x 被 k 整除，我们需要 (r + x) % k == 0。这意味着 x 必须满足 x % k = (k - r) % k。因为 r 不为0，所以 (k-r)%k 就是 k-r。我们把这个需要满足的余数 k-r 称为 “目标余数” y。

现在，最有趣的部分来了！假设我们有好几个元素，比如 a_i 和 a_j，它们需要相同的“目标余数” y。我们能在 x 等于 y 的时候同时处理它们吗？不行哦！因为每次操作后 x 都会增加，我们不能在同一个 x 值上执行两次操作。

所以，如果有 c 个元素都需要 x 满足 x % k = y，我们就必须使用 c 个不同的 x 值来处理它们。为了让 max_x 尽可能小，我们应该贪心地选择最小的、符合条件的 x 值。这些值就是： y, y + k, y + 2*k, ..., y + (c - 1)*k

对于这一组需要相同目标余数 y 的 c 个元素，我们需要的最大 x 值就是 y + (c - 1) * k。

那么，我们的整体策略就很清晰啦：

1. 遍历整个数组 a。对于那些不能被 k 整除的元素 a_i，计算出它们各自的“目标余数” y = k - (a_i % k)。
2. 用一个哈希表（在C++里就是 std::map）来统计，每个“目标余数” y 出现了多少次。我们记 counts[y] 为目标余数为 y 的元素个数。
3. 遍历这个哈希表。对于每一个 y 和它对应的次数 c = counts[y]，计算出处理完这一组元素所需要的最大 x 值，即 y + (c - 1) * k。
4. 我们在所有这些计算出的最大 x 值中，再取一个最大的，这个就是我们全局的 max_x。
5. 最终的答案就是 max_x + 1。如果所有元素一开始就能被 k 整除，那么我们不需要任何操作，max_x 可以认为是 -1，答案就是 -1 + 1 = 0。

举个例子吧！a = [1, 2, 1, 3], k = 3。

• a[0] = 1: 1 % 3 = 1。目标余数 y = 3 - 1 = 2。
• a[1] = 2: 2 % 3 = 2。目标余数 y = 3 - 2 = 1。
• a[2] = 1: 1 % 3 = 1。目标余数 y = 3 - 1 = 2。
• a[3] = 3: 3 % 3 = 0。忽略~

统计一下：

• 目标余数 1: 出现了 1 次。max_x for this group = 1 + (1-1)*3 = 1。
• 目标余数 2: 出现了 2 次。max_x for this group = 2 + (2-1)*3 = 5。

全局的 max_x 就是 max(1, 5) = 5。 所以最少的操作次数是 max_x + 1 = 5 + 1 = 6 次。是不是很简单呀，喵~

看我一爪子AC！ - 代码实现

#include <iostream>
#include <map>
#include <algorithm>

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

    // 用一个 map 来统计每种“目标余数”需要多少个元素来处理，喵~
    // key: 目标余数 y = (k - a_i % k) % k
    // value: 需要这个余数的元素数量
    std::map<long long, long long> counts;
    for (int i = 0; i < n; ++i) {
        long long val;
        std::cin >> val;
        long long rem_val = val % k;
        // 如果元素已经能被 k 整除，我们就不用管它啦
        if (rem_val != 0) {
            // 计算目标余数，并增加它的计数
            counts[k - rem_val]++;
        }
    }

    // `max_x` 用来记录我们需要用到的最大的 x 值
    // 初始化为 -1。如果不需要操作，它会保持-1，答案就是 -1 + 1 = 0
    long long max_x = -1;

    // 遍历 map，为每一组相同目标余数的元素计算它们需要的最大 x
    for (auto const& [rem, count] : counts) {
        // 对于一个目标余数 `rem`，我们有 `count` 个元素需要它
        // 为了让 max_x 最小，我们必须贪心地选择最小的 `count` 个 x 值：
        // rem, rem + k, rem + 2*k, ..., rem + (count - 1)*k
        // 这一组需要的最大 x 就是 `rem + (count - 1) * k`
        long long current_max_x = rem + (count - 1) * k;
        
        // 更新全局的 max_x，我们要取所有组中最大的那个
        if (current_max_x > max_x) {
            max_x = current_max_x;
        }
    }

    // 总操作次数是最大 x 值加 1
    // 因为 x 从 0 开始，要达到 max_x，需要 max_x 次递增，总共 max_x + 1 步
    std::cout << max_x + 1 << "\n";
}

int main() {
    // 加速输入输出，让代码跑得飞快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

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

    return 0;
}

跑得快不快呀？ - 复杂度分析

• 时间复杂度: O(N log N) 的说。 我们首先遍历 n 个元素，对于每个元素，我们向 std::map 中插入或更新一个值，这个操作的复杂度是 O(log N) 的说。所以填充 map 的总时间是 O(N log N)。之后遍历 map，map 的大小最多是 n，所以这部分也是 O(N log N) 或者更快。因此，总的时间复杂度由 map 操作主导，是 O(N log N)。如果用 std::unordered_map，平均时间复杂度可以达到 O(N) 哦！
• 空间复杂度: O(N) 的说。 在最坏的情况下，数组中所有 n 个元素对 k 的余数都不同，那么 map 中就会存储 n 个不同的键值对，所以空间复杂度是 O(N) 的说。

喵~ 记在小本本上 - 知识点与总结

这次的解题之旅，我们可以把这些宝贵的知识点记在小本本上呐：

1. 问题转化：这是一个非常重要的技巧！我们把“求最小操作次数”转化为了“求完成任务所需的最小的最大 x 值”，让问题变得更直观了。
2. 贪心策略：当有多个元素需要同一种资源（这里是特定余数的 x 值）时，为了让最终的代价（最大的 x）最小，我们应该按顺序、不浪费地分配最小的可用资源。这是一种经典的贪心思想。
3. 模运算的运用：a_i + x 能被 k 整除，等价于 x % k 需要等于一个特定的值。熟练运用模运算是解决数论问题的基础哦。
4. 使用哈希表/Map：当需要按类别统计数量时，std::map 或 std::unordered_map 是非常强大的工具，可以快速地将元素分组计数。

希望本猫娘的讲解对主人有帮助！只要多思考、多练习，任何难题都会被你轻松解决的，加油喵~ (ฅ'ω'ฅ)