poj 3258 二分

题意：看了很久才懂，有n个石头，去掉m个后，求跳两个石头或石头和岸边距离最小的最大值，就是至少要跳的距离的最大。

参考博客：

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
const int max_=5e4+5;
using namespace std;
int dis[max_];
int main()
{
    int L,n,m;
    while(~scanf("%d %d %d",&L,&n,&m))
    {
        dis[0]=0;
        dis[n+1]=L;
        int low=0,high=L;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&dis[i]);
          //  int k=fabs();
            //low=min(low,dis[i]-dis[i-1]);
        }
       /* printf("%d
",low);
        low=min(low,dis[n+1]-dis[n]);*/
        sort(dis,dis+(n+2));
        while(low<=high)
        {
            int mid=(low+high)/2;
            int ant=0;//可以去掉石头的个数
            int sum=0;
            for(int i=1;i<=n+1;i++)
            {
                sum+=dis[i]-dis[i-1];
                if(sum<=mid)
                {
                    ant++;
                }
                else
                {
                    sum=0;
                }
            }
            if(ant<=m)
                low=mid+1;
            else
                high=mid-1;
        }
        printf("%d
",low);
    }
}