A60984. 假设数组 的值域范围是 ，以下程序的时间复杂度是O(nlogn+nlogD)。1 def check(n, a, k, dist)

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

1 def check(n, a, k, dist):
2  cnt = 1
3  last = a[0]
4
5  for i in range(1, n):
6   if a[i] - last >= dist:
7    cnt += 1
8    last = a[i]
9
10  return cnt >= k
11
12 def solve(n, a, k):
13  a_sorted = a.copy()
14  a_sorted.sort()
15
16  l = 0
17  r = a_sorted[-1] - a_sorted[0]
18
19  while l < r:
20   mid = (l + r + 1) // 2
21   if check(n, a_sorted, k, mid):
22    l = mid
23  else:
24    r = mid - 1
25
26  return l
27
28 if __name__ == "__main__":
29  a = [1, 2, 8, 4, 9]
30  n = 5
31  k = 3
32  result = solve(n, a, k)
33  print(result)