CSP-S 提高级 · CSP 2023 提高级第一轮 第 18 题

3.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool f0(vector<int> &a, int m, int k) {
    int s = 0;
    for (int i = 0, j = 0; i < a.size(); i++) {
        while (a[i] - a[j] > m) j++;
        s += i - j;
    }
    return s >= k;
}

int f(vector<int> &a, int k) {
    sort(a.begin(), a.end());

    int g = 0;
    int h = a.back() - a[0];
    while (g < h) {
        int m = g + (h - g) / 2;
        if (f0(a, m, k)) {
            h = m;
        }
        else {
            g = m + 1;
        }
    }

    return g;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << f(a, k) << endl;
    return 0;
}

假设输入总是合法的且 $1 \le a_i \le 10^8, n \le 10000, 1 \le k \le \dfrac {n(n-1)} 2$，完成下面的判断题和单选题:

判断题

1. 将第 $24$ 行的 m 改为 m - 1，输出有可能不变，而剩下情况为少 $1

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

这题核心是求排序后数组里第 k 小的差值。拿到题先别急着套公式，想清楚：题目给了一个判断函数 f0，它用双指针 O(n) 算出差值≤m 的对数；外层再用二分答案找最小的 m 让 f0 返回真。所以解题主线就是：排序→二分 m→双指针验证。

最容易栽跟头的地方有三处。第一，看到 f0 里的 while 循环就以为复杂度是 O(n²)，其实双指针 j 只会单调右移，整体 O(n)。第二，时间复杂度里容易漏掉排序的 O(n log n)，把总复杂度误判成 O(n log A)。第三，改题时混淆了二分取中点的写法：(h+g)/2 和 (h+g) >> 1 在整数运算中结果完全一致，不会改变答案；而把 f0 里的 > 改成 >= 会多算一对，导致返回的 m 可能偏小，但不会变成“一定小于”。

这道题考查二分答案与双指针计数的综合应用，目标很明确：在排序后的数组 a 中，找出所有数对差值从小到大排列后的第 k 个值。

先看核心函数 f0(a, m, k)。它的作用是对排序后的 a，统计有多少对 (i, j) 满足 i > j 且 a[i] - a[j] ≤ m，然后判断这个数量是否 ≥ k。实现上用了经典的双指针技巧：外层 i 从左到右枚举右端点，内层 j 只增不减，直到 a[i] - a[j] ≤ m。此时 i - j 就是以 i 为右端点、差值不超过 m 的对数。累加所有 i - j 就是总数。因为 j 最多移动 n 次，f0 的时间复杂度是 O(n)，非常高效。

主函数 f(a, k) 负责二分搜索最小的 m。答案的范围很自然：最小可能是 0，最大可能是 a.back() - a[0]（即数组最大值减最小值）。二分框架是标准的 while(g < h)：取中点 m = g + (h - g) / 2，若 f0 返回真，说明 m 可能偏大或刚好，于是 h = m；否则 g = m + 1。循环结束时 g 就是答案。

现在逐题拆解。

小题 0：把 f0 里的 m 改成 m - 1。f0 原本判断 a[i] - a[j] > m，改成 > m - 1 后，条件变弱了，会多纳入一些差值等于 m 的对。因此 f0 返回 true 的阈值会稍微降低，但二分搜索的是“最小 m 使得 f0 为真”。由于我们找的是最小的 m，原 m 已经是最优解，再减小判定阈值并不会让答案变小（因为原 m 已经满足条件），所以输出不变；但若原 m 不是最优（比如原 m 略大），新阈值会让 f0 在更小的 m 处就返回 true，导致答案少 1。因此“有可能不变，剩下情况少 1”是正确的。

小题 1：把二分取中点的 m = g + (h - g) / 2 换成 (h + g) >> 1。在整数运算中，(h + g) / 2 和 (h + g) >> 1 是完全等价的，只是写法不同。既然 m 的值没变，f0 的调用结果也不变，二分过程完全一致，输出自然不变。正确。

小题 2：输入 5 7 2 -4 5 1 -3。先排序得到 -4, -3, 1, 2, 5, 5, 7。计算所有差值并排序：0,0,1,1,1,2,2,3,3,4,4,5,5,6,7。第 7 个（k=7）是 5，所以输出 5。正确。

小题 3：时间复杂度分析。排序占 O(n log n)。二分答案的范围是 0 ~ A-1（A = max - min + 1），二分次数是 O(log A)。每次 f0 是 O(n)。总复杂度 = O(n log n + n log A)。选项中没有直接写 O(n log n + n log A)，但 O(n log(nA)) 展开就是 O(n(log n + log A))，与之等价。所以选 C。

小题 4：把 f0 里的 > 改成 >=。原条件 a[i] - a[j] > m 改为 >= m，意味着差值等于 m 的对现在也被计入。f0 返回 true 的阈值会稍微降低（更小的 m 就能满足条件）。二分搜索的是最小 m，因此新得到的 m' 必然 ≤ 原 m。但 m' 是否严格小于原 m？不一定，因为原 m 可能已经是真正的第 k 小差值，此时即使放宽条件，最小的 m 也不会再变小。所以结论是：新输出一定小于等于原输出，但不一定严格小于。选 B。

小题 5：输入 5 8 2 -5 3 8 -12。排序后：-12, -5, 2, 3, 5, 8, 8。计算所有差值并排序：0,0,1,1,2,2,3,3,5,5,6,7,8,10,13。k = 8，第 8 个差值是 14，输出 14。选 B。