탐사 드론 충전
골드 I의견: 0
탐사 팀은 길이 \(L\) km인 직선 구간 \([0, L]\) 위에 \(N\)개의 충전소를 설치했다. 양 끝점 \(0\)과 \(L\)도 충전소 역할을 한다.
\(K\)대의 드론이 이 구간을 분담하여 탐사한다. 각 드론은 충전소 목록을 정렬했을 때 연속된 일부 충전소를 담당하며, 그 구간의 첫 번째 충전소에서 마지막 충전소까지를 비행한다. 드론이 필요한 비행 거리 (= 마지막 충전소 위치 \(-\) 첫 번째 충전소 위치)의 최댓값을 최소화하여라.
즉, \(0\), \(L\)을 포함한 모든 충전소 위치를 정렬한 뒤 \(K\)개의 연속 그룹으로 분할할 때, 각 그룹의 (마지막 위치 \(-\) 첫 번째 위치)의 최댓값을 최소화한 값을 구하여라.
- \(1 \le L \le 10^9\)
- \(0 \le N \le 200\,000\)
- \(1 \le K \le N + 2\)
- \(1 \le P_i \le L - 1\) (충전소는 구간의 내부에만 존재한다)
- 모든 \(P_i\)는 서로 다르다.
첫째 줄에 구간의 길이 \(L\), 충전소 수 \(N\), 드론 수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 충전소의 위치 \(P_1, P_2, \dots, P_N\)이 공백으로 구분되어 주어진다. \(N = 0\)이면 빈 줄이 주어진다.
드론 비행 거리 최댓값의 최솟값을 출력한다.
10 2 2
3 7
3
정렬된 위치: \(0, 3, 7, 10\). \(K=2\)대로 분할할 때 최적: \([0,3]\)과 \([7,10]\)으로 나누면 각 구간 길이가 \(3, 3\)이므로 최댓값 \(3\). 길이 \(3\)보다 작게는 불가능하므로 답은 \(3\).
12 3 3
4 6 9
3
정렬된 위치: \(0, 4, 6, 9, 12\). 3개 드론으로 최적 분할: \([0], [4,6], [9,12]\)이면 길이 \(0, 2, 3\), 최댓값 \(3\). 답은 \(3\).
riseoj 작성
출처 Original
평가 및 의견
탐사 드론 충전
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
탐사 드론 충전