R00764
공유기 설치
골드 IV레이팅
의견: 0
설명
수직선 위에 집 \(N\)채가 있다. 집의 좌표는 모두 다르다. 이 집들 중 \(C\)채에 공유기를 하나씩 설치하려고 한다.
한 곳에 공유기가 몰리면 전파가 간섭되므로, 가장 가까운 두 공유기 사이의 거리를 최대한 크게 하고 싶다. 그 최대 거리를 구하여라.
제약
\(2 \le C \le N \le 200\,000\), 좌표는 \(1\) 이상 \(10^9\) 이하의 서로 다른 정수.
입력 형식
첫째 줄에 집의 수 \(N\)과 설치할 공유기 수 \(C\)가 주어진다. 둘째 줄부터 \(N\)개의 줄에 집의 좌표가 하나씩 주어진다.
출력 형식
가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 1
입력
5 3
1
2
8
4
9
출력
3
설명
좌표 1, 4, 8 (또는 1, 4, 9)에 설치하면 인접 거리의 최솟값이 3.
예제 2
입력
2 2
1
2
출력
1
설명
두 집뿐이므로 거리는 1.
실버 II
골드 V문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
공유기 설치
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
공유기 설치
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기