CSP-J 2025 第一轮 第 27 题：程序（二）：误删排序语句可能出现的问题

题目

#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;
}

假设输入的 $a$ 数组和 $k$ 均为正整数，但 $a$ 数组不一定有序，则若误删去第 13 行的 std::sort(a + 1, a + n + 1);，程序有可能出现的问题有（ ）。

选项

• A. 输出的答案比原本答案更大
• B. 输出的答案比原本答案更小
• C. 出现死循环行为
• D. 以上均可能发生

答案

B

题解

选 B：输出的答案可能比原本答案更小。

先看 B 的反例：

``text 2 1 3 1 ``

• 保留排序：数组变成 [1, 3]，两数相差大于 k=1，输出 2。
• 删除排序：数组为 [3, 1]。处理第二个数时，1-3>1 不成立，j 仍为 0，因此 ans[2]=ans[0]+1=1。

所以答案确实可能变小。

C 不可能：循环一定会结束。

外层的 i 每次增加；内层每执行一次，j 就增加，而且有 j<i 的限制。数组是否有序，都不会导致死循环。

A 也不可能，关键在于“答案每增加一次，需要什么条件”。

先理解原程序：排序后，它求的是最少把这些数分成多少组，使每组最大值与最小值之差不超过 k。

删除排序后，由于 j 只增不减，ans[i] 也不会下降，并且每次最多增加 1。设 ans 第一次达到 1、2、3…… 的位置分别为 \[ p_1,p_2,p_3,\ldots \]

当答案第一次从 t 增加到 t+1 时，指针 j 必须越过位置 p_t，因此必然满足 \[ a[p_{t+1}]-a[p_t]>k. \]

也就是说，如果删除排序后输出 m，就能找到 m 个依次相差大于 k 的数。这些数在原程序中也必须分到不同的组，所以原程序的答案至少为 m。删除排序后的答案不可能更大。

因此只有 B 正确。