CSP-S 2023 第一轮 第28题：将第24行的“m”改为“m-1”，输出有可能不变，而剩下情况为少1。

题目

#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$，完成下面的判断题和单选题:

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

选项

• T. 正确
• F. 错误

答案

T

题解

答案：T，正确。 第 24 行指的是将 h = m; 改成 h = m - 1;。

设原程序的答案为 \(D\)，即所有数对的差的绝对值中，第 \(k\) 小的值。

f0(a, m, k) 统计差值不超过 \(m\) 的数对数量，因此：

• \(m < D\) 时，返回 false；
• \(m \ge D\) 时，返回 true。

修改后，二分过程中始终满足： \[ g\le D,\qquad h\ge D-1. \]

原因是：

• 返回 false 时，\(m<D\)，更新 g = m + 1，仍有 \(g\le D\)；
• 返回 true 时，\(m\ge D\)，更新 h = m - 1，仍有 \(h\ge D-1\)。

循环结束时 \(g\ge h\)，所以： \[ D-1\le h\le g\le D. \] 因此，输出 g 只能是 \(D\) 或 \(D-1\)。

两种情况都能出现：

第二个例子中，初始 g = 0, h = 2，取 m = 1，判断为真，修改后令 h = 0，循环立即结束并输出 0。