欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj 2456 Aggressive cows

程序员文章站 2022-06-17 20:24:35
...

题目:
poj 2456 Aggressive cows
首先把牛棚的位置x[i]按从小到大排序。牛棚数量N,牛数量为C,则每两只牛间可能的最大距离r=(x[N - 1] - x[0]) / (C - 1)。用二分法搜索0~r,判断mid满不满足条件。

AC情况:
poj 2456 Aggressive cows
代码:

#include<iostream>
#include<algorithm>
using namespace std;

int x[100005];
int N, C;

int main() {

    scanf("%d%d", &N, &C);
    for (int i = 0; i < N; i++)
        scanf("%d", &x[i]);
    sort(x, x + N);

    int l = 1, r = (x[N - 1] - x[0]) / (C - 1);
    while (r - l > 1) {
        int mid = (l + r) / 2, ans = 0;
        for (int i = 0; ans < C&&i < N;) {
            int t = i;
            while (x[++i] - x[t] < mid);
            ans++;
        }
        if (ans >= C)
            l = mid;
        else
            r = mid;

    }
    if (l != r) {
        int ans = 0;
        for (int i = 0; ans < C&&i < N;) {
            int t = i;
            while (x[++i] - x[t] < r);
            ans++;
        }
        if (ans >= C)
            l = r;

    }
    printf("%d\n", l);
    return 0;
}