중계기 증설 계획
실버 I의견: 0
일직선 도로를 따라 집 \(N\)채가 서 있고, \(i\)번째 집의 좌표는 \(x_i\)이다(모두 서로 다르다). 통신사 본부가 있는 집(좌표 \(P\), \(N\)채 중 하나)에는 이미 중계기 한 대가 설치되어 있고, 이 중계기는 옮길 수 없다.
통신사는 본부가 아닌 서로 다른 집 \(C\)채를 골라 중계기를 한 대씩 추가로 설치하려 한다. 중계기끼리 너무 가까우면 전파 간섭이 일어나므로, 설치된 모든 중계기(본부 것 포함) 중 가장 가까운 두 대 사이의 거리를 최대한 크게 만들고 싶다.
그 최소 거리의 최댓값을 구하여라.
- \(2 \le N \le 100\,000\)
- \(1 \le C \le N - 1\)
- \(0 \le x_i \le 10^9\), 좌표는 모두 서로 다르다
첫째 줄에 집의 수 \(N\), 추가로 설치할 중계기 수 \(C\), 본부의 좌표 \(P\)가 공백으로 구분되어 주어진다. \(P\)는 주어지는 집 좌표 중 하나이다.
둘째 줄에 집의 좌표 \(x_1, x_2, \dots, x_N\)이 공백으로 구분되어 주어진다.
가장 가까운 두 중계기 사이 거리의 최댓값을 출력한다.
5 2 4
1 2 4 8 9
3
본부(\(4\)) 외에 좌표 \(1\)과 \(8\)의 집에 설치하면 중계기 사이 거리가 최소 \(3\)이 된다. 최소 거리 \(4\) 이상으로는 \(2\)대를 설치할 수 없다.
2 1 0
0 10
10
남은 집이 하나뿐이므로 좌표 \(10\)에 설치하며, 최소 거리는 \(10\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
중계기 증설 계획
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
중계기 증설 계획