这段代码旨在解决这样一个问题:给定一个整数数组和一个正整数 k
,找到m值,使得数组中符合条件(差值小于等于 m)的数对数量不小于 k
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
。代码分析:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | /**************************************************************** * 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; } |