C. Dora 与 C++ 详细题解

问题重述

给定长度为 $n$ 的数组 $c$，每次操作可以选择任意一个元素增加 $a$ 或 $b$。可以执行任意次操作（包括 $0$ 次），求最终数组极差（最大值减最小值）的最小可能值。

关键观察

观察 1：$a = b$ 的情况

当 $a = b$ 时，每个元素只能增加 $a$ 的整数倍。设 $d = a = b$。

将所有元素对 $d$ 取模，得到余数 $r_i = c_i \bmod d$。由于每次操作增加 $d$，每个元素可以变成 $r_i + kd$ 的形式（$k$ 为非负整数）。

结论：最小值可以通过调整每个元素到某个区间 $[m, m + d - 1]$ 内来实现，其中 $m$ 是某个 $c_i$ 的余数加上若干倍 $d$。

观察 2：$a \neq b$ 的情况

根据裴蜀定理（Bézout's identity），存在整数 $x, y$ 使得：

$$ax + by = \gcd(a, b)$$

这意味着我们可以通过组合操作，使任意元素增加或减少 $\gcd(a, b)$。因此，问题等价于 $a = b = \gcd(a, b)$ 的情况。

设 $d = \gcd(a, b)$，则每个元素可以变成 $c_i + kd$ 的形式（$k$ 为任意整数，可以为负）。

观察 3：转化为模 $d$ 的问题

将每个元素对 $d$ 取模：

$$r_i = c_i \bmod d$$

由于可以加减 $d$ 的任意整数倍，每个元素可以变成任意与 $r_i$ 模 $d$ 同余的数。因此，问题转化为：选择 $n$ 个模 $d$ 同余类，每个类选择一个代表数，使得最大值与最小值的差最小。

观察 4：最优策略

将所有余数排序：$r_1 \le r_2 \le \dots \le r_n$。

考虑将所有数调整到区间 $[r_i, r_i + d - 1]$ 内：

• 对于 $j < i$，这些数原本余数较小，需要加上 $d$ 才能进入区间
• 对于 $j \ge i$，这些数保持原余数即可

此时，数组的最大值为 $\max(r_{i-1} + d, r_{n-1})$，最小值为 $r_i$。

极差为：

$$\text{range} = \max(r_{i-1} + d, r_{n-1}) - r_i$$

更简单的计算方式：考虑循环相邻差，最小极差为：

$$\text{ans} = \min_{i=1}^{n} ( (r_{i-1} + d) - r_i ) $$

其中定义 $r_0 = r_n - d$（循环处理）。

算法步骤

1. 计算 $d = \gcd(a, b)$
2. 将每个 $c_i$ 替换为 $c_i \bmod d$
3. 对余数数组排序
4. 初始答案 = $r_{n-1} - r_0$（最大减最小）
5. 遍历 $i = 1$ 到 $n-1$，更新答案 = $\min($答案$, r_{i-1} + d - r_i)$
6. 输出答案

时间复杂度

• 排序：$O(n \log n)$
• 遍历：$O(n)$
• 总复杂度：$O(n \log n)$

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b;
        
        int d = gcd(a, b);
        
        vector<int> r(n);
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            r[i] = x % d;
        }
        
        sort(r.begin(), r.end());
        
        int ans = r[n - 1] - r[0];
        
        for (int i = 1; i < n; i++) {
            ans = min(ans, r[i - 1] + d - r[i]);
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

代码说明

1. 计算最大公约数：gcd(a, b) 使用 C++17 的 std::gcd
2. 取模：$r_i = c_i \bmod d$
3. 排序：方便后续遍历
4. 答案计算：
   • 初始答案：排序后最大值减最小值
   • 循环相邻差：考虑将前 $i$ 个数加 $d$ 后的情况

示例验证

以第二个测试用例为例：

• $n=4, a=2, b=3$，$d = \gcd(2,3) = 1$
• $c = [1,3,4,6]$，$r = [0,0,0,0]$（因为 $d=1$，任何数模 $1$ 都是 $0$）
• 排序后 $[0,0,0,0]$，$ans = 0 - 0 = 0$

输出 $0$，与样例一致。

以第一个测试用例为例：

• $n=4, a=5, b=5$，$d = 5$
• $c = [1,3,4,4]$，$r = [1,3,4,4]$
• 排序后 $[1,3,4,4]$
• $ans = 4 - 1 = 3$
• 遍历：$i=1$: $1+5-3=3$，$i=2$: $3+5-4=4$，$i=3$: $4+5-4=5$
• 最小值 $3$，与样例一致。

总结

本题的核心技巧：

1. 利用裴蜀定理将 $a$ 和 $b$ 归约到 $\gcd(a,b)$
2. 将问题转化为模 $d$ 的余数处理
3. 排序后通过循环相邻差求最小极差
4. 时间复杂度 $O(n \log n)$