HDU4004The Frog‘s Games青蛙過河 二分

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<vector>
#include<string.h>
#include<map>
#include<cmath>
#include<queue>
#define ll long long
#define INF 0x7fffffff
#define MAX 0x3f3f3f3f
#define maxn 100005
#define mem(a) memset(a,0,sizeof(a))
#define ull unsigned long long
using namespace std;

int s[500005],L,n,m;

bool ff(int x)
{
    int ans=0,pos=0,i=1;
    while(i<=n+1)
    {
        while(s[i]-s[pos]<=x&&i<=n+1)
            i++;
        pos=i-1;
        ans++;
        if(ans>m)
            return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    int l,r,mid,k,maxx,i;
    while(cin>>L>>n>>m)
    {
       s[0]=0;
       for(i=1;i<=n;i++)
            cin>>s[i];
        s[n+1]=L;s[n+2]=3*L;
        sort(s,s+n+1);//排序
        maxx=0;
        for(i=1;i<=n+1;i++)
             maxx=max(maxx,s[i]-s[i-1]);//maxx存最大的石頭間距
        l=maxx;r=L;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(ff(mid))
            {
                k=mid;
                r=mid-1;
            }
            else
                l=mid+1;
        }
        cout<<k<<endl;
    }
    return 0;
}

           

去掉cmp比較函數就對了，否則逾時