POJ 3258：River Hopscotch (最大化最小值）

【题意】

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

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

Sample Input

25 5 2
2
14
11
21
17

Sample Output

4

分析：其实这个和Agressive Cows这道题差不多，只要把起点与终点加入到数组中，然后留下找（N-M+2）个位置之间的最大值，类比与Agressive cows的M；

具体题解可看Agressive cows



AC代码：

#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int n,m,l;
int a[51000];
bool cmp (int x,int y)
{return x<y;
}
bool C(int d)
{int last=0;for(int i=1 ; i<(n-m+2) ; i++){int crt=last+1;while(crt2&&a[crt]-a[last]<d)crt++;if(crt==n+2)return false;last = crt;}return true;}
int main()
{scanf("%d%d%d",&l,&n,&m);for(int i = 1 ; i <= n ; i++)scanf("%d",&a[i]);a[n+1]=l;sort(a,a+n+1,cmp);int en=INF;int st=0;while(en-st>1){int mid=(st+en)/2;if(C(mid))st=mid;elseen=mid;}printf("%d
",(st+en)/2);return 0;
}