POJ – 2456 Aggressive cows

题目大意:给你n个点代表牛圈的位置,然后m只牛,让你尽量将牛分开使他们的距离最远。

解法:二分呀(●´ω`●)φ

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[100005];
bool search(int d)
{
    int last=0;
    for(int i=1;i<m;i++)
    {
        int front=last+1;
        while(front<n&&a[front]-a[last]<d)
            front++;
        if(front==n)
            return false;
        last=front;
    }
    return true;
}

void solve()
{
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    //cout<<a[0];
    sort(a,a+n);
    int l=0;
    int r=1e5+5;
    while(r-l>1)
    {
        int mid=(l+r)/2;
        if(search(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%d\n",l);
}
int main()
{
    scanf("%d%d",&n,&m);
    solve();
}