POJ3258River Hopscotch（二分）

http://poj.org/problem?id=3258

题意：有一条很长很直的河距离为L，里边有n块石头，不包括起点和终点的那两块石头，奶牛们会从一个石头跳到另外一个，但因为有的石头隔得太近了，所以需要删除m块石头，来增大石头之间的最小距离。求删掉m块石头之后的其中两块石头的最小距离 。

思路 ：这个题的和3273思路代码都很像，不过这个可能难理解一点，也是二分的思路。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std ;
int main()
{
    int l,n,m ;
    while(scanf("%d %d %d",&l,&n,&m)!=EOF)
    {
        int ch[60000] ;
        for(int i = 1 ; i <= n ; i++)
            scanf("%d",&ch[i]) ;
        ch[0] = 0 ;
        ch[n+1] = l ;
        sort(ch,ch+(n+2)) ;
        int le = 0,ri = l ;//下界是一次跳跃的最短距离，上界是一次跳跃的最长距离
        for(int i = 1 ; i <= n+1 ; i++)
          le = min(ch[i]-ch[i-1],le) ;
          int mid ;
        while(le <= ri)
        {
            mid = (le+ri)/2 ;
            int cnt = 0 ,sum = 0;
            for(int i = 1 ; i < n+1 ; i++)//这里的i值到n还是n+1，最后的结果截然不同，因为去掉石头是两块石头中右边的那块
            {
                sum += (ch[i]-ch[i-1]) ;
                if(sum < mid)//如果前边的加起来比中间值还小，说明可以去掉一块石头
                cnt++ ;
                else
                sum = 0 ;
            }
            if(cnt <= m)//即使等于m了也不一定是最优解
            le = mid+1 ;
            else
            ri = mid-1 ;
        }
        printf("%d
",ri) ;
    }
    return 0 ;
}