二分答案—愤怒的牛-P1676 [USACO05FEB] Aggressive cows G

[USACO05FEB] Aggressive cows G

题目描述

农夫约翰建造了一座有 $n$ 间牛舍的小屋，牛舍排在一条直线上，第 $i$ 间牛舍在 $x_i$ 的位置，但是约翰的 $m$ 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入格式

第一行用空格分隔的两个整数 $n$ 和 $m$；

第二行为 $n$ 个用空格隔开的整数，表示位置 $x_i$。

输出格式

一行一个整数，表示最大的最小距离值。

样例 #1

样例输入 #1

5 3
1 2 8 4 9

样例输出 #1

3

提示

把牛放在 $1$，$4$，$8$ 这三个位置，距离是 $3$。容易证明最小距离已经最大。

对于 $100\%$ 的数据，$2\le n\le 10^5$，$0\le x_i\le 10^9$，$2\le m\le n$。

不保证 $a$ 数组单调递增。

题意
牛的最小距离的最大值（有限空间牛舍内牛的最大距离）
思路
距离越大 能装的牛越少

• 最小值最大化，二分答案就解
• 因为要判断距离，所以牛舍需要从小到大排个序
• 牛的个数m作为约束条件，二分答案-距离。但是题目的特色在于牛舍的距离是一定的，所以二分时是不仅要考虑到牛的个数，还要遍历牛舍的距离。但是牛舍的间隔其实无所谓，只需要满足当前牛所在的牛舍-上一个牛所在的牛舍>=要求的间距ans即可
• 其次，为了方便计算，每次将第一个牛放在第一个牛舍a0就行，因为放在第一个只会让间距更大/放更多的牛，且方便记录

数据约束
暂无
参考代码

在这里插入代码片#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N],n,m;
bool check(int t);//判断间距为t时，是不是可以装这么多牛 
int main()
{
	int ans; 
   	//n个屋舍，m个牛
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);//先把牛舍位置从小到大排好 
	int l = 0,r = a[n]-a[1];
	while(l<=r){ //不能是l<r 一个也让进 ！！！ 
		int mid = (l+r)/2; //ans = (l+r)>>1;
		if(check(mid)){
			ans = mid; //暂时定一个结果 
			l = mid + 1;//缩小范围 
		}else{
			r = mid-1;
		} 
	}
	cout<<ans;
    return 0;
}
bool check(int t){
   	int d = a[1]+t; 
    int sum=1;//判断是否有m个牛 ,第一头放在a1了 
	for(int i=2;i<=n;i++){
		if(d<=a[i]) { //当前的距离是否不小于实际的最小距离要 
			sum++;
			//当前牛位置确定了（计算下一个牛知识放在哪个位置）
			 d = a[i]+t;
		}
	} 
		return sum>=m;
	}