RiseOJ – 컨벤션

설명

농부 존이 자신의 농장에서 새로운 소 풀 먹기 컨벤션을 개최한다!

전 세계의 소들이 컨벤션에 참석해 풀을 먹기 위해 지역 공항에 도착하고 있다. 구체적으로, $$N$$ 마리의 소가 공항에 도착하며 ( $1 \leq N \leq 10^5$ ), 소 $$i$$ 는 시각 $$t_i$$ 에 도착한다 ( $0 \leq t_i \leq 10^9$ ). 농부 존은 소들을 공항에서 실어 나르기 위해 $$M$$ 대의 버스 ( $1 \leq M \leq 10^5$ )를 준비했다. 각 버스에는 최대 $$C$$ 마리의 소를 태울 수 있다 ( $1 \leq C \leq N$ ). 농부 존은 버스들과 함께 공항에서 기다리고 있으며, 도착하는 소들을 버스에 배정하려 한다. 버스는 그 버스에 탈 마지막 소가 도착한 시점에 출발할 수 있다. 농부 존은 좋은 주최자가 되고 싶으므로 도착하는 소들을 공항에서 너무 오래 기다리게 하고 싶지 않다. 농부 존이 버스를 최적으로 운용할 때, 도착하는 소들 중 최대 대기 시간의 최솟값은 얼마인가? 소의 대기 시간은 도착 시각과 배정된 버스의 출발 시각의 차이이다.

$MC \geq N$ 임이 보장된다.

출제자: Grace Cai

제약

출제자: Grace Cai

입력 형식

첫째 줄에 공백으로 구분된 세 정수 $$N$$ , $$M$$ , $$C$$ 가 주어진다. 다음 줄에 각 소의 도착 시각을 나타내는 $$N$$ 개의 정수가 공백으로 구분되어 주어진다.

출력 형식

도착하는 소들 중 최대 대기 시간의 최적 최솟값을 한 줄에 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 convention.in · 출력을 쓸 파일 convention.out

예제 1

입력

6 3 2
1 1 10 14 4 3

출력

설명

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).

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > December > Silver

올림피아드 > USACO > 2018-2019 > December > Silver

태그

JudgeUSACO

컨벤션

평가 및 의견

풀이 제출