疯牛
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
- 农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000).
但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？
将所有坐标排序，然后用二分法，检查每个间隔是否满足要求。最大间隔x[n-1]-x[0]，最小间隔0。
01.#include
<iostream>02.#include
<algorithm>03.using namespace std;04. 05.#define
MAXN 10000506. 07.int X[MAXN],N,C;08. 09.bool check(int k)10.{11.int tmp=X[0],count=1;12.for(int i=1;i<N;i++)13.{14.if(X[i]-tmp>=k)15.{16.count++;17.tmp=X[i];18.}19.if(count>=C)20.return true;21.}22.return false;23.}24. 25.int main()26.{27.while(cin>>N>>C)28.{29.for(int i=0;i<N;i++)30.cin>>X[i];31.sort(X,X+N);32.int low=0,high=X[N-1]-X[0],mid;33.while(low<=high)34.{35.mid=(low+high)/2;36.if(check(mid))37.low=mid+1;38.else39.high=mid-1;40.}41.cout<<low-1<<endl;42.}43.return 0;44.}
参考：http://blog.csdn.net/hanyuwei0/article/details/9792521