进击的奶牛

见微知著：类似于最大值最小的问题或最小值最大的问题我们可以使用二分——沃兹基硕德

此题就是求最小值最大问题，为此我们可以二分最小值，然后使用函数检查“这个最小值是否满足成为一个合格的最小值”

二分的下限我们一开始设为$0$,上限设为$最大的牛棚左边-最小的牛棚左边$ (记得排序)

如果满足的话我们肯定要将区间右移成为 $(mid,right]$

不满足的话就是相反操作(退而求其次)左移区间成为 $[left,mid]$

Ps.注意开闭区间

int l=0,r=a[n]-a[1]+1,mid;
while(l<=r){
	//TODO
	mid=(l+r)>>1;
	if(check(mid)){
		ans=mid;
		l=mid+1;
	}else{
		r=mid-1;
	}
}

检查函数的内容为：是否至少有$m$个牛棚两两之间间距至少大于等于$x$ (这个不难想出)

bool check(ll x){
//是否至少有m个牛棚两两之间间距至少大于等于x
	int t=1,last_cow=a[1];//记录有多少个牛棚可以两两之间距大于等于x
	//last_cow存储上一个牛住在牛棚的坐标
	for(int i=2;i<=n;i++){
		if(a[i]-last_cow>=x){
			t++;
			last_cow=a[i];
		}
	}
	if(t>=m){return 1;}
	else{return 0;}
}

最后.谢谢你阅读这篇题解