Feb Gold 愤怒的牛
题目描述
原题来自：USACO 2005 Feb. Gold
农夫约翰建造了一座有n间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在xi的位置，但是约翰的m头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。
牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？
输入格式
第一行用空格分隔的两个整数n和m；
第二行为n个用空格隔开的整数，表示位置xi。
输出格式
输出仅一个整数，表示最大的最小距离值。
样例
样例输入
5 3 1 2 8 4 9
样例输出
3
样例解释
把牛放在1,4,8这样最小距离是3。
数据范围与提示
2≤n≤10^5,0≤xi≤10^9,2≤m≤n。
题意：简单的说就是给你一段长度，在这一段中给出m个点，然后在这m个点中选出k个点，让这k个点之间相邻两个点的之间距离的最小值最大
解题思路：
首先，我们看题目要求的两头牛之间的最小距离的最大值，显然这是二分中常见的最大化最小值题目。
然后通过二分枚举这个最小值，然后通过贪心的思想找出满足要求的最大的这个最小值
具体来说，我们可以先令C(d)表示可以安排牛的位置，并使最近两头牛的距离不小于d。
那么问题就转化为满足C（d）的最大的d，另外，最近的间距不小于d也可以看成是所有牛的间距都不小于d，因此就可以用C(d)表示可以安排牛的位置，并使最近两头牛的距离不小于d。
显然应该采用贪心的思想。
先对牛舍的位置进行排序，牛舍之间的最小值最大为最后那个牛舍的位置减去第一个隔间的位置，这样的话我们就可以二分了，判断每俩头牛之间最小相距mid距离时，能否装下m头牛，如何判断也是一个值得注意的地方，肯定要把第一个牛舍的位置放一头牛，然后判断下一个牛舍的位置与上一个放牛的位置的距离是否大于等于mid，符合条件则放入，并把上一个放牛的位置改为当前位置，最后输出结果就行了
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
int a[MAXN];
int n,m;
bool judge(int dis){
int num=1,p=a[0];
for(int i=1;i<n;i++){//搜索是否满足条件
if(a[i]-p>=dis){
num++;
p=a[i];
if(num==m) return true;
}
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
int l=0,r=a[n-1]-a[0];
int mid;
int ans;
while(l<=r){
mid=(l+r)>>1;
if(judge(mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%d\n",ans);
return 0;
}