Home » 国际竞赛 » Details

USACO 2018 December Contest Silver 1 Convention

Category: 国际竞赛, 计算机国际竞赛 Date: 2018年12月20日下午12:23

Farmer John is hosting a new bovine grass-eating convention at his farm!

Cows from all over the world are arriving at the local airport to attend the convention and eat grass. Specifically, there are
cows arriving at the airport ( ) and cow arrives at time ( ). Farmer John has arranged ( ) buses to transport the cows from the airport. Each bus can hold up to cows in it ( ). Farmer John is waiting with the buses at the airport and would like to assign the arriving cows to the buses. A bus can leave at the time when the last cow on it arrives. Farmer John wants to be a good host and so does not want to keep the arriving cows waiting at the airport too long. What is the smallest possible value of the maximum waiting time of any one arriving cow if Farmer John coordinates his buses optimally? A cow’s waiting time is the difference between her arrival time and the departure of her assigned bus.

It is guaranteed that .

INPUT FORMAT (file convention.in):

The first line contains three space separated integers , , and . The next line contains space separated integers representing the arrival time of each cow.

OUTPUT FORMAT (file convention.out):

Please write one line containing the optimal minimum maximum waiting time for any one arriving cow.

SAMPLE INPUT:

632
1 1 10 14 4 3

SAMPLE OUTPUT:

If the two cows arriving at time 1 go in one bus, cows arriving at times 2 and 4 in the second, and cows arriving at times 10 and 14 in the third, the longest time a cow has to wait is 4 time units (the cow arriving at time 10 waits from time 10 to time 14).

Problem credits: Grace Cai

USACO 2018 December Contest Silver 1 Convention题解(翰林国际教育提供，仅供参考)

显然满足二分性质，二分一个时间 $x$ ，每个车上的牛需要满足两个条件：
个数 <= $c$ ，最晚减去最早 <= $x$ ，计算出最小的车数，然后和 $m$ 比较。

#include <bits/stdc++.h>
using namespace std;
int n, m, c;
int a[100020];
bool ok(int x) {
    int cnt = 0;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n && j - i < c) {
            if (a[j] - a[i] > x) {
                break;
            }
            j++;
        }
        cnt++;
        i = j;
    }
    return cnt <= m;
}
int main() {
    freopen("convention.in", "r", stdin);
    freopen("convention.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    int L = -1;
    int R = 1e9;
    while (L < R - 1) {
        int M = (L + R) / 2;
        if (ok(M)) {
            R = M;
        } else {
            L = M;
        }
    }
    printf("%dn", R);
    return 0;
}