传送门

思路

二分答案。最小值最大，我们想到的肯定是最大化查找（即 $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;
}

本题二分答案

二分查找每一个可能的$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<bits/stdc++.h>
using namespace std;
int a[200005],c,n,l,r;
int ch(int x){
	int z=1,w=a[1];
	for(int i=2;i<=n;i++) {
		if(a[i]-w>=x) {
			w=a[i];
			z++;
		}
	}
	return z>=c;
}
int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	l=0,r=1e9+7;
	while(l+1<r) {
		int mid=(l+r)/2;
		if(ch(mid)) {
			l=mid;
		}else{
			r=mid;
		}
	}
	cout<<l;
	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());
}