传送门：POJ 2456
Description
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi
Output
* Line 1: One integer: the largest minimum distance
Sample Input
5 3
1
2
8
4
9Sample Output
3Hint
OUTPUT DETAILS:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
Huge input data,scanf is recommended.
题意：约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。
代码1：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const int INF=1e9;
int x[maxn];
int N,M;bool C(int d){int last=0;for(int i=1;i<M;i++){int crt=last+1;while(crt<N&&x[crt]-x[last]<d){crt++;}if(crt==N) return false;last=crt;}return true;
}void solve(){//最开始时对x数组排序sort(x,x+N);//初始化解的存在范围int lb=0,ub=INF;while(ub-lb>1){int mid=(lb+ub)/2;if(C(mid)) lb=mid;else ub=mid;}printf("%d\n",lb);}int main()
{scanf("%d%d",&N,&M);for(int i=0;i<N;i++)scanf("%d",&x[i]);solve();return 0;
}
又学了一遍二分，有新的收获，又重新写了一份代码,注释部分是另一种写法，并非错误代码，如下
代码2:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int x[maxn];
int n,c;/*
//从隔间的角度进行分析，判断在最小距离d的情况下，能否将c个牛全部安置下来
bool C(int d){ //表示可以安排的牛的位置使得任意两头牛的距离都不小于dint crt=1,last=0; //安置了crt个牛，牛的上次安置坐标为x[last]for(int i=1;i<n;i++){if(x[i]-x[last]>=d){ //如果当前位置和牛的上次安置位置距离大于等于d，就可以在这个位置安置一个牛crt++;last=i;}if(crt>=c) return true; //如果所有的牛都安置了，说明当前这个距离d可以作为最小距离}return false;
}
*///从牛的角度
bool C(int d){ //表示可以安排的牛的位置使得任意两头牛的距离都不小于dint last=0,crt; //牛的上次安置坐标为x[last]for(int i=1;i<c;i++){crt=last+1;while(crt<n&&x[crt]-x[last]<d){ //寻找合理的本次牛安置的位置crt++;}if(crt>=n) return false; last=crt; }return true;
}void solve(){sort(x,x+n);int l=0,r=x[n-1]+1;int ans=-1;while(r>=l){ //只要区间不为空，就可以继续搜索答案。因为[l,r]里的任一个数都有可能是答案。int mid=l+(r-l)/2;if(C(mid)){ans=mid;l=mid+1;}else r=mid-1;}printf("%d\n",ans);
}/*
void solve(){sort(x,x+n);int l=0,r=x[n-1]+1;while(r-l>1){ //答案范围[l,r)，l（小写L）一定满足条件，所以只要搜索区间等于1了，答案也就唯一确定了，就是lint mid=l+(r-l)/2;if(C(mid)) l=mid;else r=mid;}printf("%d\n",l);
}
*/int main(){scanf("%d%d",&n,&c);for(int i=0;i<n;i++){scanf("%d",&x[i]);}solve();return 0;}