leetcode-go/bailian/2456.aggressive-cows/main.cc

#include <algorithm>
#include <cstdio>

using namespace std;

int n, c, a[100005];

int search(int l, int r) {
  while (1 < r - l) {
    int mid = l + (r - l) / 2, x = a[1], k = 1;
    for (int i = 2; i <= n; i++) {
      if (mid <= a[i] - x) {
        x = a[i];
        if (c <= ++k) break;
      }
    }
    if (c <= k)
      l = mid;
    else
      r = mid;
  }
  return l;
}

int main() {
  scanf("%d %d", &n, &c);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  sort(a, a + n);
  printf("%d\n", search(0, a[n] - a[1]));
  return 0;
}