7249 : 정답 이분탐색 1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 집 좌표가 주어질 때, $C$개의 공유기를 설치하여 인접한 두 공유기 사이의 거리 중 최솟값이 최대가 되도록 하십시오.
이 문제는 매개변수 탐색(Parametric Search)으로 풀 수 있습니다: 최솟값 $d$를 이분탐색하여 $d$ 이상의 간격으로 $C$개를 배치할 수 있는지 확인합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
이 문제는 매개변수 탐색(Parametric Search)으로 풀 수 있습니다: 최솟값 $d$를 이분탐색하여 $d$ 이상의 간격으로 $C$개를 배치할 수 있는지 확인합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 집의 개수 $N$과 공유기 개수 $C$가 주어집니다. ($2 \le C \le N \le 100{,}000$)
둘째 줄부터 $N$개의 줄에 집의 좌표가 주어집니다. ($0 \le$ 좌표 $\le 10^9$)
둘째 줄부터 $N$개의 줄에 집의 좌표가 주어집니다. ($0 \le$ 좌표 $\le 10^9$)
출력 설명
가장 가까운 두 공유기 사이의 거리가 최대가 되도록 했을 때, 그 거리를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1
2
8
4
9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
집 좌표를 정렬한 후, 이분탐색으로 최소 간격 $d$를 탐색합니다. 검사 함수: 첫 번째 집부터 순서대로 $d$ 이상 떨어진 집을 선택하며, $C$개 이상 선택 가능한지 확인합니다.