골드 III설명
일직선 도로 위의 서로 다른 \(N\)개의 위치 \(x_1, x_2, \dots, x_N\) 중에서 \(K\)곳을 골라 통신 기지국을 세우려고 한다. 기지국끼리 전파가 간섭하지 않도록, 선택한 기지국들 중 가장 가까운 두 기지국 사이의 거리가 되도록 커지게 만들고 싶다.
\(K\)곳의 위치를 적절히 골랐을 때 얻을 수 있는, 가장 가까운 두 기지국 사이 거리의 최댓값을 구하여라.
제약
\(2 \le K \le N \le 200{,}000\)
\(1 \le x_i \le 10^9\)
모든 \(x_i\)는 서로 다르다.
입력 형식
첫째 줄에 위치의 수 \(N\)과 세울 기지국의 수 \(K\)가 주어진다.
다음 \(N\)개의 줄에 각각 위치의 좌표 \(x_i\) (\(1 \le x_i \le 10^9\))가 주어진다. 모든 좌표는 서로 다르다.
출력 형식
가장 가까운 두 기지국 사이 거리의 최댓값을 출력한다.
예제 1
입력
5 3
1 2 8 4 9
출력
3설명
위치 1, 4, 8(또는 9) 을 고르면 인접 거리가 3과 4이므로 최소 거리가 3이다. 더 크게 만들 수는 없으므로 답은 3이다.
예제 2
입력
4 2
10 1 5 20
출력
19설명
기지국 2개는 양 끝 1과 20을 골라 거리 19를 얻는 것이 최선이다.
문제 정보
riseoj 작성
출처 Original
태그