题目描述 Description
小徐从美国回来后，成为了USACO中国区的奶牛销售代理商，专门出售质优价廉的“FJ”牌奶牛。上题中，小徐终于凑够了钱，把她的小伙伴们接过来。
现在，她需要给她自己和其他3个伙伴安排房间。在同一直线上有N间房子（2<=N<=10^5），每间房子有一个唯一的位置（即X坐标）Xi。
（0<=Xi<=10^9）。为了方便交流，请你写一个程序，安排4间房子，使它们的最远距离最短。
输入描述 Input Description
第一行：一个正整数N
第二行：N个正整数，Xi,空格隔开
输出描述 Output Description
最短的最远距离
样例输入 Sample Input
7
1 7 4 20 13 2 11
样例输出 Sample Output
3（选择1、2、4、7）
数据范围及提示 Data Size & Hint
这个。就是二分。
设f（x）为最远距离为x时能否安排4间房子
这个函数当然有单调性，所以，果断二分搜索x。
代码：
#include<cstdio> #include<algorithm> using namespace std; int n,a[100001],ans; bool pd(int x) { int b[100001],i; for(i=1;i<=n;i++) b[i]=1; for(i=2;i<=n;i++) if(a[i]-a[i-1]<=x&&b[i]<b[i-1]+1) { b[i]=b[i-1]+1; if(b[i]>=4) return 1; } return 0; } int main() { int i,j,l,r=0,mid; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); l=1; r=a[n]-a[1]; while(l<=r) { mid=(l+r)>>1; if(pd(mid)) r=mid-1; else l=mid+1; } printf("%d",l); return 0; }