陶陶是个贪玩的孩子，他在地上丢了A个瓶盖，为了简化问题，我们可以当作这A个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出B个，使得距离最近的2个距离最大，他想知道，最大可以到多少呢？
输入格式：
第一行，两个整数，A,B。（B<=A<=100000）
第二行，A个整数，分别为这A个瓶盖坐标。
输出格式：
仅一个整数，为所求答案。
5 3 1 2 3 4 5
2
限时3秒
思路：
二分答案；
每次二分一个答案，然后check；
check时，每次选择最小的大于等于mid的线段，如果够B个则为真；
否则是假；
最后输出，轻松ac；
来，上代码：
#include <cstdio> #include <iostream> #include <algorithm> #define maxn 100005 using namespace std; int if_z,A,B,dis[maxn],ans; char Cget; inline void read_int(int &now) { now=0,if_z=1,Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) { if(Cget==‘-‘) if_z=-1; Cget=getchar(); } while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); } now*=if_z; } bool check(int size) { int now=dis[1],cnt=1; for(int i=2;i<=A;i++) { if(dis[i]-now>=size) { cnt++; now=dis[i]; } } if(cnt>=B) return true; else return false; } int main() { read_int(A),read_int(B); for(int i=1;i<=A;i++) read_int(dis[i]); sort(dis+1,dis+A+1); int l=0,r=dis[A]-dis[1],mid; while(l<=r) { mid=(l+r)>>1; if(check(mid)) { ans=mid; l=mid+1; } else r=mid-1; } cout<<ans<<endl; return 0; }
原文：http://www.cnblogs.com/IUUUUUUUskyyy/p/6413932.html