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;}