[杂七杂八] POJ3258（二分）

题意：
有一群牛要过河，河长L，河中有N块石头，每块石头离河边Di远，现在要去掉M块石头，求剩下的石头之间以及石头与河岸的最小距离的最大值。
题解：
看代码。

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int MAXN=50000+10;int L,n,m;int a[MAXN];int check(int x){    int k=0,i=1,last=0;    for(i=1;i<=n+1;i++)    if(a[i]-a[last]<x)//注意这里是用前面的石头跟后面的石头计算距离（起点是在河边的，你不可能一开始就删除河边吧？）     k++;    else    last=i;//如果两个石头之间的距离大于二分出来的答案的话，就保存下来，与下一块石头计算距离     if(k>m)    return 1;    else    return 0;}int erfen(){    int l=0,r=L,ans=0;    while(r>=l)    {        int mid=(l+r)/2;        if(check(mid))//如果删除的石头大于m的话，就说明最小距离过大了         r=mid-1;        else         {            ans=mid;            l=mid+1;        }    }    return ans;}int main(){    while(~scanf("%d%d%d",&L,&n,&m))    {        memset(a,0,sizeof(a));        for(int i=1;i<=n;i++)        scanf("%d",&a[i]);        a[0]=0;//开始的点         a[n+1]=L;//终点         sort(a,a+n+2);//把始点和终点放进去。         printf("%d\n",erfen());    }}