CSP-J 2025 第一轮 第 26 题：程序（二）：n=100,k=2,a={1..100} 时的输出

题目

#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=100$、$k=2$、$a = \{1, 2, \dots, 100\}$ 时，输出为（ ）。

选项

• A. $34$
• B. $100$
• C. $50$
• D. $33$

答案

A

题解

答案是 A．34。

排序、去重后，数组仍为 \(a[i]=i\)，\(n=100\)。

内层循环的条件为： \[ a[i]-a[j+1]>2 \quad\Longleftrightarrow\quad i-j-1>2. \] 所以循环结束时，\(j=\max(0,i-3)\)。

ans 是全局数组，初始值全为 \(0\)，因此：

• \(i=1,2,3\) 时，\(j=0\)，ans[i] = 1；
• \(i\ge4\) 时，ans[i] = ans[i-3] + 1。

也就是说，ans 的值每三个数增加一次： ``text i： 1 2 3 | 4 5 6 | 7 8 9 | … | 97 98 99 | 100 ans[i]： 1 1 1 | 2 2 2 | 3 3 3 | … | 33 33 33 | 34 ``

最终输出： \[ \boxed{\text{ans}[100]=\left\lceil\frac{100}{3}\right\rceil=34} \]