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