#1#农夫和他的奶牛（poj2456 二分）

**

#1#农夫和他的奶牛（poj2456 二分）

**

（题外话：这是菜鸡F的第一篇博客！作为一个身为计算机专业学子却羞耻的是个纯粹的编程小白的F也是有一个伟大的理想和一颗坚持奋斗的心的！今天开始写博客，记录自己多多少少的成长。三十年河东三十年河西，莫欺少年穷。那么我们一起加油吧！）

//
有n个牛栏，选m个放进牛，相当于一条线段上有 n 个点，选取 m 个点，
使得相邻点之间的最小距离值最大
思路：贪心+二分
二分枚举相邻两牛的间距，判断大于等于此间距下能否放进所有的牛。
//

这道题一开始没有读懂题。后来看了别人的题目分析才明白a[n]数组的用处是储存牛栏隔间的编号，相隔距离即编号的差值。所以首先需要对隔间编号进行排序。而后利用二分法依次缩小寻找最小距离的最大值的范围。最后找出答案。

这是学了二分法以后的第一次应用。在此附上二分法的核心代码：

while(l<=r)      //l为最小值，r为最大值
{
	mid=l+(r-l)/2;
	if(judge(mid))l=mid+1;
	else r=mid-1;
} 

二分查找法的时间复杂度为:O(log2n)

以下为该题完整代码

#include<iostream>
#include<cstdio> 
#include<cstring>
#include<algorithm>
using namespace std;
int const MAXN = 1000000;
int n,cow,a[MAXN];
bool judge(int dis){                 //检验该距离是否能放入所有牛
	int cc=a[0],count=1;             //放入第一头牛
	for(int j = 1;j < n;j++){
		if(a[j]-cc >= dis) {
			count++;                 //如果下一个隔间与上一个隔间的间距满足要求 则放入一头牛
			cc=a[j];
		}
		if(count >= cow) return true;
	}
	return false;
}
void distance(){                  //二分查找最小距离的最大值
	int l=1,r=a[n-1]-a[0];
	while(l<r){
		int mid=l+(r-l)/2;
		if(judge(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<r<<endl;
}
int main(){
	while(cin>>n>>cow){
		for(int i=0;i<n;i++)
			cin>>a[i];
		sort(a,a+n);
		distance();
	}
	return 0;
}