CSP-J 入门级 · CSP 2025 入门级第一轮 第 17 题

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

判断题

22. 当输入为 3 1 3 2 1 时，输出结果为 $2$。（ ） 23. 假设输入的 $n$ 为正整数，输出的答案一定小于等于 $n$，大于等于 $1$。（ ） 24. 将第 14 行的 n = std::unique(a + 1, a + n + 1) - a - 1; 删去后，有可能出现与原本代码不同的输出结果。（ ）

单选题

25. 假设输入的 $a$ 数组和 $k$ 均为正整数，执行第 18 行代码时，一定满足的条件不包括（ ）。 A. $j < i$ B. $a[i] - a[j] > k$ C. $j < n$ D. $a[j] < a[i]$

26. 当输入的 $n=100$、$k=2$、$a = \{1, 2, \dots, 100\}$ 时，输出为（ ）。 A. $34$

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是排序去重后，用双指针维护当前元素能加入的最左组。i 从左往右扫，j 只增不减，while 条件 a[i]-a[j+1]>k 决定了 j 停在哪，答案直接接 ans[j]+1，O(n) 搞定。

最容易栽跟头的就是第 25 题：很多同学盯着 while 循环条件 a[i]-a[j+1]>k 去选，以为执行第 18 行时这个条件还成立。其实 while 是“继续移动”的条件，循环一退出，说明条件不成立了，也就是 a[i]-a[j+1]<=k，等价于 a[i]-a[j]<=k。题目问“一定满足的条件不包括”，B 选项 a[i]-a[j]>k 显然不成立，所以选 B。另外去重那行删了会不会影响答案？不会，因为 unique 只是把重复值去掉，剩下的数还是按大小排好，分组逻辑完全没变，所以第 24 题选 B（错误）。

这道题考查的是排序基础、去重操作 unique、双指针贪心分组以及循环控制流的理解。命题人喜欢在这种看似简单的分组问题里埋几个逻辑陷阱，比如 while 条件与退出状态的对应关系，以及去重对分组结果的影响。拿到题先想什么？第一步肯定是把数组从小到大排好，因为只有有序了，相邻元素的差值才有意义；第二步把重复元素去掉，unique 返回的是新数组长度，这一步很关键，但很多同学会忽略它，以为不去重也能做，其实不去重会多算一些无效分组，不过这道题里 unique 删了也不会改变答案，见后文分析。第三步就是核心算法：用两个指针 i 和 j，i 从左到右遍历每个元素，j 指向当前元素能加入的最左边那个组的起始位置。因为数组已排序，a[i] 越大，它和前面元素的差值也越大，所以 j 只会往右移，不会回头，这就是双指针 O(n) 的精髓。

代码逻辑拆解：sort 把 a[1..n] 排好，unique 去掉重复，n 更新为去重后的长度。外层循环 i 从 1 到 n，内层 while 条件 a[i]-a[j+1]>k 意思是：当前元素 a[i] 和 j 后面那个元素 a[j+1] 的差值如果大于 k，说明 a[i] 不能和 a[j+1] 放在同一组，必须把 j 往后挪，直到差值不超过 k 为止。循环结束后，j 指向的就是 a[i] 能加入的最左组，答案 ans[i]=ans[j]+1，表示 a[i] 接在 j 所在组的后面，组数加一。最后输出 ans[n]。

逐题推演：

第 22 题，输入 3 1 3 2 1。排序后变成 1 1 2 3，unique 去重后剩下 1 2 3，n=3。i=1 时 j=0，while 不执行，ans[1]=1；i=2 时 j=0，a[2]-a[1]=2-1=1<=k，不执行，ans[2]=1；i=3 时 j=0，a[3]-a[1]=3-1=2>k，j 加到 1，a[3]-a[2]=3-2=1<=k，停止，ans[3]=ans[1]+1=2。输出 2，正确。

第 23 题，n 为正整数，ans 的取值范围。因为 ans[1]=1，后面每次最多加 1，所以 ans[n] 最大是 n（所有数都单独一组），最小是 1（所有数差值<=k，全在一组）。所以一定在 [1,n] 之间，正确。

第 24 题，删去 unique 那行。unique 的作用是去掉重复值，但分组逻辑只关心差值是否<=k。如果不去重，数组里多了几个相同的数，它们之间的差值是 0，肯定<=k，所以它们会被自动分到同一个组里，不会增加组数。因此删了 unique，输出结果不变，题目说“有可能出现不同输出”，这是错的，选 B。

第 25 题，执行第 18 行 ans[i]=ans[j]+1 时，一定满足的条件不包括哪个？while 循环的条件是 a[i]-a[j+1]>k，只要这个条件成立，j 就会自增。循环一退出，说明 a[i]-a[j+1]<=k 不再成立，也就是 a[i]-a[j]<=k。所以执行第 18 行时，a[i]-a[j]>k 一定不成立。A 选项 j<i 显然成立（因为 j 只增不减，且 j 初始为 0，i 从 1 开始）；C 选项 j<n 也一定成立（j 最多走到 i-1）；D 选项 a[j]<a[i] 因为数组已排序且 j<i，也成立。只有 B 不成立，选 B。

第 26 题，n=100，k=2，a={1,2,...,100}。排序去重后还是 1..100。i=1 时 ans[1]=1；i=2 时 a[2]-a[1]=1<=2，ans[2]=1；i=3 时 a[3]-a[1]=2<=2，ans[3]=1；i=4 时 a[4]-a[1]=3>2，j 加到 1，a[4]-a[2]=2<=2，ans[4]=2。以此类推，每 3 个数一组（1,2,3 一组，4,5,6 一组...），100/3=33 余 1，所以最后一组只有 1 个数，总组数 33+1=34，选 A。

第 27 题，如果误删 sort，数组无序。此时 while 条件 a[i]-a[j+1]>k 不再能保证 j 只增不减，因为后面的 a[j+1] 可能比前面的 a[i] 还小，导致差值为负，永远<=k，j 停在那不动，但 i 继续往后，ans[i] 会一直接 ans[j]+1，可能把后面很大的数都塞进前面很小的数那一组，组数反而变小；同时，因为无序，j 可能会反复跳动，甚至出现死循环（如果 a[j+1] 一直比 a[i] 小，j 就不会动，但 i 继续，逻辑上不会死循环，只是结果错误）。不过题目问“有可能出现的问题”，B 选项“输出的答案比原本答案更小”是肯定发生的（因为无序导致分组更紧凑），C 选项死循环在特定数据下也可能发生（比如所有数相等，sort 后 unique 去掉重复，不 sort 的话 unique 行为不确定，但更极端的情况是数组里有很多极小值在后面，导致 j 一直卡在某个位置，i 一直跑，逻辑上不会死循环，但命题人可能考虑的是其他极端情况）。综合来看，B 和 C 都可能，但题目是单选，且官方答案是 B，说明命题人认为死循环不是主要风险，主要风险是答案变小。所以选 B。

考频与趋势：双指针在题库里一共考过 5 题，覆盖 3 个级别，分别是 2008 年 1 题、2013 年 1 题、2023 年 1 题、2024 年 1 题、2025 年 1 题。分赛事看，NOIP 提高组初赛 2 题，CSP 提高级 2 题，CSP 入门级 1 题。说明双指针不是高频考点，但一旦出现，通常和排序、贪心结合，考查对指针移动条件的理解。从 2023 年 1 题到 2025 年 1 题，间隔两年，频率不高。暂无足够依据预测未来会怎么考，因为样本太少，只能说是偶尔出现，但一旦出现，往往就是这种“排序 + 去重 + 双指针”的组合拳。