poj 3258 River Hopscotch (二分搜索---最大化最小值)

思路：函数 can(int x)判断当前的距离x能不能得到。用贪心的策略来选取N-M个点来看是否满足。

注意边界条件和边界数据：

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
using namespace std;  
const int MAXN=50005;  
int L,N,M,d[MAXN];  
bool can(int mid)  
{  
    int num=N-M;  
    int last=0;  
    for(int i=0;i<num;i++){  
        int cur=last+1;  
        while(cur<=N && d[cur]-d[last]<mid){  
            cur++;  
        }  
        if(cur>N) return 0;  
        last=cur;  
    }  
    return 1;  
}  
int main()  
{  
        while(cin>>L>>N>>M)  
        {  
            if(N+M==0)  
            {cout<<L<<endl;continue;}  
            d[0]=0;  
            for(int i=1;i<=N;i++)  
                scanf("%d",&d[i]);  
            d[N+1]=L;  
            if(N==M){  
                cout<<L<<endl;  
                continue;  
            }  
            sort(d+1,d+1+N);  
            int lhs=0,rhs=L;  
            while(rhs-lhs>1)  
            {  
                int mid=(lhs+rhs)>>1;  
                if(can(mid)) lhs=mid;  
                else rhs=mid;  
            }  
            cout<<lhs<<endl;  
        }  
          
    return 0;  
}

补充：软件开发 , C++ ,