#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) 将第24行的“m”改为“m-1”，输出有可能不变，而剩下情况为少1。（ ）
2) 将第22行的“g +(h-g)/2”改为“(h+g)>>1”，输出不变。（ ）
3) 当输入为“5 7 2 -4 5 1 -3”，输出为”5”。（ ）
选择题
4) 设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（ ）
5) 将第10行中的“>”替换为“>=”，那么原输出与现输出的大小关系为（ ）
6) 当输入为“5 8 2 -5 3 8 -1 2”时，输出为（ ）