QQ扫一扫联系
#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≤ ai≤108,nle10000,1≤k≤,完成下面的判断题和单选题:
将第 24 行的 m 改为 m - 1,输出有可能不变,而剩下情况为少 1。()
将第 22 行的 g + (h - g) / 2 改为 (h + g) >> 1,输出不变。()
当输入为 5 7 2 -4 5 1 -3,输出为 5。()
设 a 数组中最大值减最小值加 1 为 A,则 f 函数的时间复杂度为()。
O(nlogA)
O(n2logA)
O(nlog(nA))
O(nlogn)
将第 10 行中的 > 替换为 >=,那么原输出与现输出的大小关系为()。
一定小于
一定小于等于且不一定小于
一定大于等于且不一定大于
以上三种情况都不对
当输入为 5 8 2 -5 3 8 -12,输出为()。
13
14
8
15