POJ2456 Aggressive cows（二分+贪心）

February 28, 2016

题目链接

题意：给定 n 个农舍的位置和 m 头牛，每头牛放到不同的农舍使得任意两头牛距离的最小值最大。

二分距离然后贪心遍历判断是否能够取到。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
int n, c;
bool judge(int x){
    int cnt = 0;
    int l = 1, r = 2;
    int flag = 0;
    while(l<n){
        int cha = a[r]-a[l];
        if(cha>=x){
            if(l == flag)
                cnt++;
            else cnt += 2;
            flag = r;
            l = r;
            r = l+1;
        }else{
            r++;
            if(r>n)
                break;
        }
    }
//cout << cnt << endl;
    if(cnt >= c)
        return 1;
    return 0;

}

int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d%d", &n, &c) != EOF){
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        sort(a+1, a+1+n);

        a[0] = 0;
        int l = 0, r = a[n];

        while(l<=r){
            int mid = l+(r-l)/2;
            if(judge(mid))
                l = mid+1;
            else r = mid-1;
        }
        cout << r << endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]