排序: 首先对数组进行升序排序。排序的目的是为了方便后续使用双指针法来快速计算满足条件的数对数量。
二分查找:
- 确定搜索范围: 最小的差值为 0，最大的差值为数组最大值与最小值的差。
- 中间值判断: 对于每个中间值 m，调用函数 f0 来判断是否存在至少 k 对元素的差值小于等于 m。
- 调整搜索范围: 如果存在至少 k 对，说明可以找到更小的 m，缩小右边界；否则，增大左边界。
双指针计算:
- 函数 f0 中使用双指针来快速计算给定差值 m 下满足条件的数对数量。
- 两个指针 i 和 j 分别从数组开头和开头开始遍历。
- 当 a[i] - a[j] > m 时，移动 j 指针，直到差值小于等于 m。
- i 和 j 之间的元素构成的所有数对都满足条件，直接累加到 s 中。

关键函数

f0(vector<int> &a, int m, int k):
- 输入：数组 a，差值 m，所需数对数量 k。
- 输出：是否存在至少 k 对元素的差值小于等于 m。
f(vector<int> &a, int k):
- 输入：数组 a，所需数对数量 k。
- 输出：满足条件的最小差值。

代码分析：

/**************************************************************** 
 * Description: 2023_CSP_S_R03
 * Author: Alex Li
 * Date: 2024-06-17 09:56:38
 * LastEditTime: 2024-09-13 00:53:33
****************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 函数 f0 判断给定的差值 m 是否可以使得数组中符合条件（差值小于等于 m）的数对数量不小于 k
bool f0(vector<int> &a, int m, int k) {
    int s = 0;  // 用来记录符合条件的数对数量
    // 双指针遍历数组
    for (int i = 0, j = 0; i < a.size(); i++) {
        // 当当前数对的差值 a[i] - a[j] 大于 m 时，增大 j，使得差值小于等于 m
        while (a[i] - a[j] > m)
            j++;
        // i 和 j 之间的所有数对都是合法的，累加这些数对的数量
        s += i - j;
    }
    // 返回是否符合条件：数对的数量是否不小于 k
    return s >= k;
}

// 函数 f 用二分法找到最小的 m 使得符合条件（差值小于等于 m）的数对数量恰好不小于 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;  // 计算中间值 m
        // 调用 f0 检查当前的 m 是否可以满足条件
        if (f0(a, m, k)) {
            h = m;  // 如果满足，收缩上界
        } else {
            g = m + 1;  // 如果不满足，增大下界
        }
    }
    return g;  // 返回找到的最小 m
}

int main() {
    int n, k;
    cin >> n >> k;  // 输入数组大小 n 和所需的数对数量 k
    vector<int> a(n, 0);
    // 读取数组元素
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // 输出符合条件的最小差值
    cout << f(a, k) << endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Topic