7259 : 케이크 자르기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 케이크 조각이 있고, $M$명 이상에게 동일한 길이로 분배하려 합니다.
각 조각을 자유롭게 자를 수 있을 때, 나누어 줄 수 있는 조각의 최대 길이를 구하십시오.
이분탐색으로 조각 길이를 탐색하고, 그 길이로 $M$명 이상에게 줄 수 있는지 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
각 조각을 자유롭게 자를 수 있을 때, 나누어 줄 수 있는 조각의 최대 길이를 구하십시오.
이분탐색으로 조각 길이를 탐색하고, 그 길이로 $M$명 이상에게 줄 수 있는지 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 케이크 조각 수 $N$과 사람 수 $M$이 주어집니다. ($1 \le N, M \le 100{,}000$)
둘째 줄에 각 케이크 조각의 길이가 주어집니다. (각 길이 $\le 10^9$)
둘째 줄에 각 케이크 조각의 길이가 주어집니다. (각 길이 $\le 10^9$)
출력 설명
$M$명 이상에게 동일한 길이로 분배하기 위해 자를 수 있는 최대 조각 길이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 6
6 3 3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
이분탐색 범위: 0부터 최대 조각 길이. 검사 함수: 길이 $L$로 자를 때 총 조각 수 $= \sum_{i} \lfloor \text{cake}_i / L \rfloor \ge M$인지 확인합니다.