관측소 배치

시간 제한: 2000 ms메모리 제한: 256 MBSilver V3작성자: Super Admin매개 변수 탐색이분 탐색최대-최소 최적화

일직선 위에 K개의 후보 지점이 있다. 이 중 M개의 지점에 관측소를 세우려 한다. 인접한 두 관측소 사이의 거리 중 최솟값을 최대화하도록 M개의 지점을 선택하시오.

단, 후보 지점의 좌표는 정수이며, 첫 번째와 마지막 후보 지점에는 반드시 관측소를 세워야 한다.

입력

첫째 줄에 후보 지점의 수 K와 세울 관측소의 수 M이 공백으로 구분되어 주어진다. (2 <= M <= K <= 50)
둘째 줄에 K개의 후보 지점의 좌표가 공백으로 구분되어 주어진다. (0 <= 좌표 <= 1,000,000,000, 오름차순으로 주어짐)

출력

인접한 두 관측소 사이 거리의 최솟값의 최댓값을 출력한다.

문제 통계

8

전체 제출

8

정답

100%

정답률

1

정답자 수

비슷한 문제

입력 1

5 3
1 3 5 7 9

출력 1

입력 2

4 2
1 2 3 100

출력 2

정렬 후 이분 탐색 조합

Platinum V6.5