CSP-J 2025 第一轮 第 22 题：程序（二）：输入 3 1 3 2 1 时输出是否为 2

题目

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

当输入为 3 1 3 2 1 时，输出结果为 $2$。（ ）

选项

• √. 正确
• ×. 错误

答案

√

题解

选 √，正确，输出确实为 2。

输入 3 1 3 2 1 表示：

• n = 3，k = 1；
• 数组为 [3, 2, 1]。

排序后数组为 [1, 2, 3]，去重后不变，n 仍为 3。ans 是全局数组，初始值均为 0。

注意：j 初始为 0，并且会保留上一轮的值。

最后输出 ans[3]，即 2。