택배 회사의 새 물류 센터에는 일렬로 늘어선 택배 보관함 \(N\) 개가 있다. \(i\) 번째 보관함은 직선 위의 정수 좌표 \(x_i\) 에 놓여 있으며, 모든 좌표는 서로 다르다.

오늘 배달해야 할 짐이 \(C\) 개 있는데, 같은 보관함에 두 짐을 넣을 수는 없다. 서로 다른 짐들의 알림 신호가 간섭하지 않으려면, 이웃한 두 짐이 들어간 보관함 사이의 거리가 가능한 한 멀어야 한다.

\(C\) 개의 짐을 서로 다른 보관함에 배정할 때, 가장 가까운 두 짐 사이의 거리(즉, 선택한 보관함 좌표들을 정렬했을 때 인접한 두 좌표 차이의 최솟값) 를 최대로 만들고 싶다. 이때 가능한 최댓값을 구하라.

예를 들어 보관함이 좌표 \(1, 2, 4, 8, 9\) 에 있고 짐이 \(3\) 개라면, \(1, 4, 8\) 번 좌표에 넣으면 인접 간격이 \(3, 4\) 가 되어 최소 간격이 \(3\) 이다. 이보다 더 큰 최소 간격은 만들 수 없으므로 답은 \(3\) 이다.

\(2 \le C \le N \le 100{,}000\)

\(0 \le x_i \le 1{,}000{,}000{,}000\) 이며 모든 \(x_i\) 는 서로 다르다.

첫째 줄에 보관함의 개수 \(N\) 과 짐의 개수 \(C\) 가 공백으로 구분되어 주어진다 (\(2 \le C \le N \le 100{,}000\)).

둘째 줄부터 \(N\) 개의 줄에 걸쳐 각 보관함의 좌표 \(x_i\) 가 한 줄에 하나씩 주어진다 (\(0 \le x_i \le 1{,}000{,}000{,}000\)). 모든 좌표는 서로 다르다.

가장 가까운 두 짐 사이의 거리의 최댓값을 한 줄에 출력한다.

riseoj 작성

출처 Original