CSP-J 2025 第一轮 第 25 题：程序（二）：执行内层 for 循环时一定满足的条件不包括

题目

#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$ 均为正整数，执行第 18 行代码时，一定满足的条件不包括（ ）。

选项

• A. $j < i$
• B. $a[i] - a[j] > k$
• C. $j < n$
• D. $a[j] < a[i]$

答案

B

题解

答案是 B。第 18 行是 ans[i] = ans[j] + 1;，执行它时，内层循环已经结束。

注意两个关键点：

• a 是全局数组，所以 a[0] = 0。
• 排序、去重后，a[1] < a[2] < ... < a[n]，且它们都是正整数。

逐项分析：

A．j < i 一定成立。 当 j = i - 1 时，内层循环判断中的差值为 \[ a[i]-a[j+1]=a[i]-a[i]=0, \] 不可能大于正整数 k，所以 j 不会增加到 i。

B．a[i] - a[j] > k 不一定成立。 j 可能始终为 0，此时没有条件保证 a[i] - a[0] > k。例如输入： ``text 1 2 1 ` 执行第 18 行时，i = 1，j = 0`，于是 \[ a[i]-a[j]=1-0=1\le 2. \] 因此 B 不成立。

C．j < n 一定成立。 由 j < i 且 i ≤ n，可得 j < n。

D．a[j] < a[i] 一定成立。 若 j ≥ 1，由数组严格递增及 j < i 可得；若 j = 0，则 a[0] = 0 < a[i]。

这道题的关键是：不要漏掉 j = 0 的情况。