愤怒的牛

二分答案 + 贪心校验。是一行读入全部坐标。

1. 先把牛舍坐标排序；
2. 二分猜测一个最小距离mid；
3. check贪心：第一头牛放在第一个牛舍，往后遇到和上一头牛距离≥mid 就放一头，统计能放多少头牛；
4. 如果能放下≥m 头牛，说明这个距离可行，记录答案，继续尝试更大距离；否则缩小距离。
   #include<bits/stdc++.h>
   using namespace std;
   const int N = 1e5 + 10;
   long long a[N]; // 坐标最大1e9，改用long long防止溢出
   int n, m; // n牛舍数量，m牛的数量

// check：判断最小距离d是否可行，能不能放下至少m头牛
bool check(long long d){
int cnt = 1; // 已经放了1头牛，第一间牛舍放第一头
long long last = a[1];// 上一头牛放置的位置
for(int i = 2; i <= n; i++){
if(a[i] - last >= d){
cnt++;
last = a[i];
}
}
return cnt >= m;
}

int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a+1, a+1+n); // 牛舍坐标从小到大排序
long long l = 0, r = a[n] - a[1]; // 二分左右边界：最小距离0，最大距离首尾差
long long res = 0; // 保存答案，最大的最小距离
while(l <= r){
long long mid = l + (r - l) / 2; // 二分中点，防溢出写法
if(check(mid)){
res = mid; // 这个距离可行，记录答案
l = mid + 1; // 尝试更大距离
}else{
r = mid - 1; // 距离太大放不下，缩小
}
}
cout << res << endl;
return 0;
}