假设数组 $a$ 的值域范围是 $D$，以下程序的时间复杂度是 $O(n\log n+n\log D)$。

1bool 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                                                                      15int 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                                                                      33int 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}