#PU858. USACO 2018 December Contest, Silver — Problem 1. Convention

    ID: 1258 传统题 文件IO:convention 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:dec18来源:usaco.orgscoring:equal_test_cases二分答案贪心

USACO 2018 December Contest, Silver — Problem 1. Convention

USACO 2018 December Contest, Silver — Problem 1. Convention

题目描述

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 NN cows arriving at the airport (1≤N≤1051 \leq N \leq 10^5) and cow ii arrives at time tit_i (0≤ti≤1090 \leq t_i \leq 10^9). Farmer John has arranged MM (1≤M≤1051 \leq M \leq 10^5) buses to transport the cows from the airport. Each bus can hold up to CC cows in it (1≤C≤N1 \leq C \leq N). 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 MC≥NMC \geq N.

输入格式

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

输出格式

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

数据范围

(见题面原文)

样例

样例 1

6 3 2
1 1 10 14 4 3
4
If the two cows arriving at time 1 go in one bus, cows arriving at times 3 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