실버 II알파카 목장에는 일직선 도로를 따라 N개의 축사가 있다. \(i\)번째 축사는 좌표 \(x_i\)에 위치한다.
목장 주인은 사나운 알파카 C마리를 이 축사들 중 서로 다른 C곳에 한 마리씩 배치하려고 한다. 알파카끼리 너무 가까이 있으면 서로 싸우기 때문에, 배치된 알파카들 중 가장 가까운 두 마리 사이의 거리가 최대가 되도록 배치하고 싶다.
알파카를 가장 적절하게 배치했을 때, 가장 가까운 두 알파카 사이 거리의 최댓값을 구하여라. 두 축사 \(x_i, x_j\) 사이의 거리는 \(|x_i - x_j|\) 이다.
- \(2 ≤ C ≤ N ≤ 200\,000\)
- \(0 ≤ x_i ≤ 1\,000\,000\,000\)
- 모든 \(x_i\)는 서로 다르다.
첫째 줄에 축사의 개수 \(N\)과 배치할 알파카의 수 \(C\)가 공백으로 구분되어 주어진다.
둘째 줄에 \(N\)개의 축사 좌표 \(x_1, x_2, \dots, x_N\)이 공백으로 구분되어 주어진다. 모든 좌표는 서로 다르다.
가장 가까운 두 알파카 사이 거리의 최댓값을 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
서브태스크 1 | 30점 | \(N \le 1{,}000\) |
서브태스크 2 | 70점 | 추가 제약 조건 없음 |
5 3
1 2 4 8 93축사 좌표는 {1, 2, 4, 8, 9}이다. 알파카 3마리를 좌표 1, 4, 8에 배치하면 가장 가까운 두 마리 사이의 거리는 3이 된다. 이보다 더 멀리 떨어뜨릴 수는 없으므로 답은 3이다.
5 5
1 2 4 8 91알파카 5마리를 5개의 축사 모두에 배치해야 한다. 이때 인접한 좌표 1과 2 사이의 거리 1이 가장 가까운 거리이므로 답은 1이다.
2 2
10 1000000000999999990알파카 2마리를 좌표 10과 1,000,000,000에 배치하면 거리는 999,999,990이며 이것이 최댓값이다.
rip 작성
출처 Original