레이팅 미적용설명
수직선 위에 집 \(N\)채가 있다. 집의 좌표는 모두 다르다. 이 집들 중 \(C\)채에 공유기를 하나씩 설치하려고 한다.
한 곳에 공유기가 몰리면 전파가 간섭되므로, 가장 가까운 두 공유기 사이의 거리를 최대한 크게 하고 싶다. 그 최대 거리를 구하여라.
제약
\(2 \le C \le N \le 200\,000\), 좌표는 \(1\) 이상 \(10^9\) 이하의 서로 다른 정수.
입력 형식
첫째 줄에 집의 수 \(N\)과 설치할 공유기 수 \(C\)가 주어진다. 둘째 줄부터 \(N\)개의 줄에 집의 좌표가 하나씩 주어진다.
출력 형식
가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 1
입력
5 3
1
2
8
4
9
출력
3
설명
좌표 1, 4, 8 (또는 1, 4, 9)에 설치하면 인접 거리의 최솟값이 3.
예제 2
입력
2 2
1
2
출력
1
설명
두 집뿐이므로 거리는 1.
골드 IV문제 정보
riseoj 작성
출처 Original
태그