二分+贪心

对牛与牛之间的距离进行二分查找

每次查找到mid时进行判断,判断mid是否合法^[1].若合法,则说明可能有更大的合法距离,向上查找.若非法,则说明>=mid的距离均非法,向下查找.

最后二分出来的答案即最大(的最小)距离

AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,a[100100];
bool ck(int d){//判断是否合法
	int k=1,t=a[1]+d;//第一头牛放在第一个位置(a[1]),第二头牛放在(a[1]+d)的位置上
	for(int i=2;i<=n;i++){
		if(a[i]<t)continue;//判断我们输入的位置中是否符合我们需要的位置(t);不符合就进行下一个位置的判断
		k++;t=a[i]+d;//符合的话牛棚的个数(k)就加一;t为我们需要的下一个牛棚的位置
	}if(k>=m)return 1;//如果我们判断出来的牛棚的个数(k)大于或者等于我们需要的牛棚个数就返回1
	else return 0;
}
int main(){cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);//快排函数,我们肯定是从小开始往大找的
    l=0,r=a[n]-a[1];//l为最小(的最小)距离(0);r为最大(的最小)距离(最远的牛棚减去最近的牛棚)
	while(l<=r){
		int mid=(l+r)>>1;
		if(ck(mid))l=mid+1;//判断是否合法
		else r=mid-1;
	}cout<<r;//输出最大(的最小)距离
	return 0;//好习惯
}