传送门

思路

二分答案。最小值最大，我们想到的肯定是最大化查找（即 $l$ 在可行区）。然后二分查找每一个 $x_i$，判断是否符合所有牛都可以住下。复杂度 $\mathcal O\left(n\log n\right)$。

AC code

#include<iostream>
#include<algorithm>
using namespace std;
int x[int(1e5+5)],n,m;
bool check(int xxx){
	int cnt=1,id=1;
	for(int i=2;i<=n;i++){
		if(x[i]-x[id]>=xxx)cnt++,id=i;
	}
	return cnt>=m;
}
int upper(){
	int l=0,r=x[n]-x[1]+1;
	while(l+1<r){
		int mid=l+r>>1;
		if(check(mid))l=mid;
		else r=mid;
	}
	return l;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x[i];
	}
	sort(x+1,x+n+1);
	cout<<upper();
	return 0;
}