A67882. 下面程序的时间复杂度是（ ），假设数组 的值域范围是D。1 #include <iostream>

下面程序的时间复杂度是（ ），假设数组 的值域范围是D。

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