A67912. 假设数组 的值域范围是D，以下程序的时间复杂度是O(nlogn+nlogD)。1 bool check(int n, int a[], int k, int dist) {

假设数组 的值域范围是D，以下程序的时间复杂度是O(nlogn+nlogD)。

1 bool check(int n, int a[], int k, int dist) {
2  int cnt = 1;
3  int last = a[0];
4
5  for (int i = 1; i < n; i++) {
6   if (a[i] - last >= dist) {
7    cnt++;
8    last = a[i];
9   }
10  }
11
12  return cnt >= k;
13 }
14
15 int solve(int n, int a[], int k) {
16  std::sort(a, a + n);
17
18  int l = 0;
19  int r = a[n - 1] - a[0];
20  
21  while (l < r) {
22   int mid = (l + r + 1) / 2;
23
24   if (check(n, a, k, mid))
25    l = mid;
26   else
27    r = mid - 1;
28  }
29
30  return l;
31 }
32
33 int main() {
34  int a[] = {1, 2, 8, 4, 9};
35  int n = 5;
36  int k = 3;
37
38  std::cout << solve(n, a, k) << std::endl;
39
40  return 0;
41 }