假设数组的值域范围是D，代码如下：

bool check(int n, int a[], int k, int dist) {
  int cnt = 1;
  int last = a[0];
  for (int i = 1; i < n; i++) {
    if (a[i] - last >= dist) {
      cnt++;
      last = a[i];
    }
  }
  return cnt >= k;
}
int solve(int n, int a[], int k) {
  std::sort(a, a + n);
  int l = 0;
  int r = a[n - 1] - a[0];
  while (l < r) {
    int mid = (l + r + 1) / 2;
    if (check(n, a, k, mid))
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}
int main() {
  int a[] = {1, 2, 8, 4, 9};
  int n = 5;
  int k = 3;
  std::cout << solve(n, a, k) << std::endl;
  return 0;
}