P1676 [USACO05FEB] Aggressive cows G 题解

题目传送门

解题思路

最大值最小化问题，考虑二分答案。

首先要排序，保证序列单调不降，然后求出两个隔间之间的距离。

sort(a+1,a+1+n);
for(ri i=1;i<=n;i++)
	dis[i]=a[i+1]-a[i];

二分出一个 \(mid\)，判断它是否合法：每次累加距离，如果距离和比 \(mid\) 大，说明当前可以分配牛，记录数量；再把距离和归零，方便下次计算。最后比较可以分配牛的数量与牛的数量，如果前者大于等于后者，则说明当前 \(mid\) 合法。

int check(int mid){
	int sum=0,cnt=1;
	for(ri i=1;i<=n;i++){
		sum+=dis[i];
		if(sum>=mid){
			sum=0;
			cnt++;
		}
		if(cnt>=m)return 1;
	}
	return 0;
}

如果当前 \(mid\) 合法，求出最大的 \(mid\)，左端点变为 \(mid+1\)，否则右端点变为 \(mid-1\)，进一步缩小范围。

int l=1,r=1e9;
while(l<=r) {
	int mid=l+r>>1;
	if(check(mid)){
		ans=max(ans,mid);
		l=mid+1;
	}
	else r=mid-1;
}