POJ 2456 Aggressive cows---二分搜索法

///3.最大化最小值

/**

    POJ 2456 Aggressive cows

    Q:一排牛舍有N (2 <= N <= 100,000) 个，位置为x1,...,xN (0 <= xi <= 1,000,000,000)

    为使牛之间不受到伤害，需最大化他们之间的距离，求最大化最近两头牛之间的距离

    共M只牛

    A：

    条件C(x):可以使得最近两头牛之间的距离不小于d->求满足条件的最大d->如何高效的判断C(x)

*/

#include"iostream"

#include "cstdio"

#include "algorithm"

using namespace std;

#define MAX 100010

#define INF 0x3f3f3f3f

int N,M,x[MAX];

bool C(int d)

{

    int last=;///首位定放牛；看能否找到M-1个牛舍 能够满足之间距离>=d?

    for(int i=;i<M;i++)

    {

        int crt=last+;///cnt表示当前牛舍位置下标

        while(crt<N&&x[crt]-x[last]<d)///last表示上一被占牛位舍位置下标，

        {

            crt++;

        }

        if(crt==N)return false;///牛舍不能满足

        last=crt;

    }

    return true;

}

void solve()

{

    int lb=,ub=INF;

    int mid;

    while(ub-lb>)

    {

        mid=(lb+ub)/;

        if(C(mid))///放得下，距离还可以再大点

            lb=mid;

        else    ///放不下了,mid已经不能满足

            ub=mid;

    }

    printf("%d\n",lb);

}

int main()

{

    while(~scanf("%d%d",&N,&M))

    {

        for(int i=;i<N;i++)

        {

            scanf("%d",&x[i]);

        }

        sort(x,x+N);

        solve();

    }

}