CSP-J 2025 第一轮 第 24 题：程序（二）：删去去重语句是否影响输出

题目

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int n, k;
int a[200007];
int ans[200007];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    std::sort(a + 1, a + n + 1);
    n = std::unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1, j = 0; i <= n; ++i) {
        for (; j < i && a[i] - a[j + 1] > k; ++j)
            ;
        ans[i] = ans[j] + 1;
    }
    printf("%d\n", ans[n]);
    return 0;
}

将第 14 行的 n = std::unique(a + 1, a + n + 1) - a - 1; 删去后，有可能出现与原本代码不同的输出结果。（ ）

选项

• √. 正确
• ×. 错误

答案

×

题解

答案是 ×（错误）。删掉去重语句，会增加对重复元素的计算，但不会改变最终输出。

先看循环在做什么。排序后，j 不断右移，直到剩下的这段 a[j + 1] ... a[i] 满足最大值与最小值之差不超过 k。因此，

``cpp ans[i] = ans[j] + 1; ``

表示前面的元素用 ans[j] 组处理，最后这一段再作为一组。对于非负的 k，程序求的是将排序后的数分组、每组最大值与最小值之差不超过 k 时的最少组数。

重复值不会增加所需的组数：保留一个值以后，其余相同的数都可以放进包含这个值的同一组，不会改变该组的最大值或最小值。因此，去重前后最少组数相同。

也可以直接从代码理解。排序后相同的数一定相邻。若 a[i] == a[i - 1]，在非负 k 的情况下，上一轮停止时满足的条件这一轮仍然满足，所以 j 不变，得到的 ans[i] 也与 ans[i - 1] 相同。重复元素只是重复得到同一个结果，不会多增加一组。

例如，k = 2，排序后的数组为：

``text 1 1 3 3 6 ``

保留重复值时可分成 [1, 1, 3, 3]、[6]，共两组；去重后是 1 3 6，可分成 [1, 3]、[6]，仍然是两组。

题面没有写出 k 的范围。如果考虑 k < 0，排序后只要 j < i，就有 a[i] - a[j + 1] >= 0 > k，所以每轮都会让 j 增加到 i。这时赋值实际是 ans[i] = ans[i] + 1；由于全局数组初始为零且每个位置只赋值一次，各项均为 1，去重前后输出也相同。

所以，std::unique 在这里减少了重复元素带来的计算，删除它不会产生不同的输出，题目中的说法错误。