POJ 3258 River Hopscotch 二分
来源：http://poj.org/problem?id=3258
题意：有一条河，河的长度已知，河中间有一些石头，石头的数量知道，相邻两块石头之间的距离已知。现在可以移除一些石头，问移除m块石头后，相邻两块石头之间的距离的最小值最大是多少。
思路：二分枚举答案。每 次二分枚举一个值，判断该值能够去掉多少块石头。二分枚举求上限。
代码：
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;const int N = 50010;LL num[N];int main(){//freopen("1.txt","r",stdin);LL len;int n,m;while(scanf("%lld%d%d",&len,&n,&m) != EOF){ memset(num,0,sizeof(num)); num[0] = 0; for(int i = 1; i <= n; ++i) scanf("%lld",&num[i]); num[n+1] = len; sort(num,num+n+2); LL lp = 0,rp = len,aans = 0; while(lp < rp){ int cnt = 0; int ans = n - m + 1; LL mmid = (lp + rp) / 2; for(int i = 1,j = 0; i <= n + 1; ){ if(num[i] - num[j] <= mmid){ cnt++; i++; } else{ j = i;i++; } } if(cnt > m) rp = mmid; else lp = mmid + 1; } printf("%lld\n",lp);}return 0;}