poj2456 110ms 二分+贪心

#include<cstdio>
#include<algorithm>
//二分，很多需要注意的地方
const int Maxn = 1e5;
int stalls[Maxn+5];
int n,c;
int cnt,tmp;
bool Judge(int dis)
{
    cnt = 1,tmp = stalls[0];
    for(int i = 1; i<n; ++i)
    {
        if(stalls[i]-tmp>=dis)
        {
            cnt++;
            tmp = stalls[i];
            if(cnt>=c)
                return true;
        }
    }
    return false;
}
int BinarySearch()
{
    int L = 1;
    int R = stalls[n-1]-stalls[0];
    int mid;
    while(L<=R)
    {
        /*
        mid =  L + (R-L) >> 1;
        错误写法，因为加法的优先级比右移大，所以会出现死循环
          若L = 2,R = 3,mid = 1，而不是2，所以死循环了
        */
        //正确写法：
        mid = L +((R-L)>>1);
        if(Judge(mid))
            L = mid + 1;
        else
            R = mid - 1;
    }
    return L-1;
}
int main()
{
    scanf("%d%d",&n,&c);
    for(int i = 0; i<n; ++i)
        scanf("%d",&stalls[i]);
    std::sort(stalls,stalls+n);
    printf("%d\n",BinarySearch());
    return 0;
}