CSP-J 2025 第一轮 第 23 题：程序（二）：输出是否一定在 1 到 n 之间

题目

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

假设输入的 $n$ 为正整数，输出的答案一定小于等于 $n$，大于等于 $1$。（ ）

选项

• √. 正确
• ×. 错误

答案

√

题解

选 √，正确。

设输入的数量为 \(N\)，排序、去重后代码中的 n 变为 \(m\)。由于 \(N>0\)，有 \[ 1\le m\le N。 \]

关键看： ``cpp ans[i] = ans[j] + 1; ``

ans 是全局数组，初始值全部为 0。处理第 \(i\) 项时，内层循环保证 \(0\le j\le i\)：

• 若 \(j<i\)：通过归纳，前面算出的值满足 \(0\le ans[j]\le j\)，所以

\[ 1\le ans[i]=ans[j]+1\le j+1\le i。 \]

• 若 \(j=i\)：此时 ans[i] 尚未赋值，仍为 0，因此执行 ans[i] = ans[i] + 1 后得到 1，也满足上述范围。（题目未限制 k 非负，所以要考虑这种情况。）

因此，每一项都有 \(1\le ans[i]\le i\)，最终输出满足 \[ \boxed{1\le ans[m]\le m\le N} \] 所以题目说法正确。