순환 도로의 충전소
실버 II의견: 0
둘레가 \(L\)인 원형 순환 도로가 있다. 도로 위의 위치는 한 기준점에서 시계 방향으로 잰 거리 \(0\) 이상 \(L-1\) 이하의 정수로 나타낸다.
현재 전기차 충전소 \(N\)개가 서로 다른 위치 \(p_1, \dots, p_N\)에 있다. 시는 예산으로 충전소를 최대 \(K\)개까지 새로 지을 수 있으며, 새 충전소도 정수 위치에만 지을 수 있다.
충전소를 적절히 추가하여, 도로를 따라 인접한 두 충전소 사이 거리(호의 길이)의 최댓값을 최소로 만들고 싶다. 그 최솟값을 구하여라.
- \(1 \le N \le 100\,000\), \(N \le L \le 10^9\)
- \(0 \le K \le 10^9\)
- \(0 \le p_i < L\), 위치는 모두 서로 다른 정수이다
첫째 줄에 도로의 둘레 \(L\), 기존 충전소의 수 \(N\), 새로 지을 수 있는 충전소의 최대 개수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 기존 충전소의 위치 \(p_1, p_2, \dots, p_N\)이 공백으로 구분되어 주어진다.
만들 수 있는 '인접 충전소 간 최대 거리'의 최솟값을 출력한다.
10 3 1
0 3 7
3
호의 길이는 \(3, 4, 3\)이다. 길이 \(4\)인 호에 충전소 하나를 추가하면 가장 긴 간격이 \(3\)이 된다. 간격 \(2\) 이하로 만들려면 충전소가 \(3\)개 필요하다.
12 2 0
0 6
6
충전소를 추가할 수 없으므로 답은 현재 가장 긴 간격인 \(6\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
순환 도로의 충전소
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
순환 도로의 충전소