7265 : 이분탐색 마스터
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수가 주어질 때, 이를 $K$개의 연속 그룹으로 분할하여 각 그룹 내 최대 간격(gap)의 최솟값을 구하십시오.
이분탐색으로 허용 최대 간격을 탐색하고, 해당 간격으로 $K$개 이하의 그룹으로 나눌 수 있는지 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
이분탐색으로 허용 최대 간격을 탐색하고, 해당 간격으로 $K$개 이하의 그룹으로 나눌 수 있는지 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정수의 개수 $N$과 그룹 수 $K$가 주어집니다. ($1 \le K \le N \le 100{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
$K$개의 연속 그룹으로 분할할 때, 그룹 내 최대 간격의 최솟값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
1 3 6 10 15
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
정렬 후 인접 원소 간 간격을 구합니다. 이분탐색으로 허용 최대 간격을 탐색하며, 간격이 허용값보다 크면 새 그룹으로 분리합니다. 그룹 수가 $K$ 이하면 조건 충족입니다.