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

/*A.题
牛要到河对岸，在与河岸垂直的一条线上，河中有N块石头，给定河岸宽度L，以及每一块石头离牛所在河岸的距离，

现在去掉M块石头，要求去掉M块石头后，剩下的石头之间以及石头与河岸的最小距离的最大值。

注意题目给的距离不一定是按照从小到大的顺序给的，所以需要给距离排序。

做题思想：二分所求的最小距离的最大值mid，记录可以去掉的石头块数cnt

根据cnt和M的大小关系来决定减去哪部分区间。代码：
*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
const int N = 50010;
int arr[N];
int main()
{
    int L,n,m;
    scanf("%d%d%d",&L,&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",arr+i);
    }
    arr[0]=0;
    arr[n+1]=L;
    sort(arr,arr+n+2);
    int lef=1,rig=L+1,mid,curr;
    while(rig-lef>1)
    {
        mid=(lef+rig)>>1;//最小距离
        int last=0,cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(arr[i]-arr[last]<mid)
            {
                cnt++;
            }
            else
            {
                last=i;
            }
        }
        if((last!=0)&&(arr[n+1]-arr[last]<mid)) cnt++;
        if(cnt>m) rig=mid;
        else lef=mid;
    }
    printf("%d\n",lef);

}