poj 2456 Aggressive cows && nyoj 疯牛 最大化最小值 二分

题目链接：

nyoj : http://acm.nyist.net/JudgeOnline/problem.php?pid=586

poj : http://poj.org/problem?id=2456

思路：

二分答案，从前到后依次排放m头牛的位置，检查是否可行

代码：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

using namespace std;

const int maxn = 1e5+5;

const int INF = 1e9;

int a[maxn];

int n,m;

bool check(int d) {

    int pos,pre;

    pre=0;

    for(int i=0;i<m-1;++i) {

        pos=pre+1;

        while(pos<n&&a[pos]-a[pre]<d) {pos++;}

        if(pos==n) return false;

        pre=pos;

    }

    return true;

}

int main() {

    while(~scanf("%d %d",&n,&m)) {

        for(int i=0;i<n;++i) scanf("%d",&a[i]);

        sort(a,a+n);

        int l=0,r=INF,mid,ans;

        while(l<=r) {

            mid=(l+r)>>1;

            if(check(mid)) ans=mid,l=mid+1;

            else r=mid-1;

        }

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

    }

    return 0;

}