f (d[i+1]-d[i]<min)
min = d[i+1]-d[i];
left = min, right = l;
while(left<=right)
{
mid=(left+right)/2;
if (judge(mid))
{
left=mid+1;
ans=mid;
}
else
right=mid-1;
}
cout<<ans<<endl;
return 0;
}
将此源程序提交给POJ 3258 “River Hopscotch”，可以Accepted。
【例2】好斗的牛（POJ 2456 翻译而来）。
题目描述
农夫约翰建造了一座有n（2<=n<=100000）间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在xi（0<=xi<=1000000000）的位置。但是约翰的c（2<=c<=n）头牛不喜欢牛舍这种布局，而且几头牛如果冲到同一个隔间里，它们就要发生争斗。约翰为了防止牛之间互相攻击互相伤害，因此决定把每头牛都放在离其它牛尽量远的牛舍，使任意两头牛之间的最小距离尽可能大，那么，这个最大的最小距离是多少呢？
输入格式
第一行是用空格分隔的两个整数n,c
第二行为n个用空格隔开的整数，表示位置xi
输出格式
输出仅一个整数，表示最大的最小距离值
样例输入
5 3
1 2 8 4 9
样例输出
3
样例解释
把牛放在第1，4， 8 间，这样最小的距离值是3
（1）编程思路。
将C头牛放在N个点中的C个点上的最大距离是：dis=(Pmax-Pmin)/(C-1)。（最大的坐标-最小的坐标再除以C-1）。
首先对隔间位置xi从小到大排序，然后以left=0为下界，以right=dis为上界通过二分法求这个最大的最小距离。
假设当前的最小距离为mid，如果判断出最小距离为mid时可以放下C头牛，就先让mid变大再试试，即增大下界（left=mid+1）；如果放不下C头牛，说明当前的mid太大了，就先让mid变小再进行判断，即减小上界（right=mid-1）。直到求出一个最大的mid就是最终的答案。
（2）源程序。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int p[N], n, c;
bool judge(int x)
{
int cnt = 1, tmp = p[0];
for(int i = 1; i < n; i++)
{
if(p[i] - tmp >= x)
{
cnt++;
tmp = p[i];
if(cnt >= c) //可以放下C头牛
return true;
}
}
return false;
}
int main()
{
int i,low,high,mid;
cin>>n>>c;
for(i=0;i<n;i++)
scanf("%d",&p[i]);
sort(p,p+n);
high=(p[n-1]-p[0])/(c-1);
low=0;
while(low<=high)
{
mid=(low+high)/2;
&nbs