本题二分答案

二分查找每一个可能的$dis$

判断是否符合所有牛都可以住下
不符合就让$r$左移，符合就让$l$右移并更新$ans$

显而易见，$ans$最后一定是最优结果

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,c,dis[N];
bool check(int ds){
	int cnt=1,place=0;
	for(int i=1; i<n; i++){
		if(dis[i]-dis[place]>=ds){
			place=i;
			cnt++;
		}
	}
	if(cnt>=c)return true;
	return false;
}
int main(){
	cin>>n>>c;
	for(int i=0; i<n; i++)
		cin>>dis[i];
	sort(dis,dis+n);
	int l=0,r=dis[n-1]-dis[0],ans=0;
	while(l<r){
		int mid=l+(r-l)/2;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid;
	}
	cout<<ans;
	return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x7fffffff;
int n,m,a[100001];
int solve(){
    int l=0,r=inf,mid,now,tot;
    while(l<r){
        mid=(l+r+1)>>1;
        now=a[1];
        tot=1;
        for(int i=2;i<=n;++i){
            if(a[i]-now>=mid)now=a[i],++tot;
            if(tot>=m)break;
        }
        if(tot<m)r=mid-1;
        else l=mid;
    }
    return l;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    printf("%d",solve());
}