7250 : 정답 이분탐색 2
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 수하물 컨테이너를 순서를 바꾸지 않고 $M$개의 트럭에 나누어 실을 때, 한 트럭이 감당해야 하는 최대 무게의 최솟값을 구하십시오.
이분탐색으로 최대 적재 무게를 가정하고, $M$대 이하로 나눌 수 있는지 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
이분탐색으로 최대 적재 무게를 가정하고, $M$대 이하로 나눌 수 있는지 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 수하물 컨테이너 수 $N$과 트럭 수 $M$이 주어집니다. ($1 \le M \le N \le 100{,}000$)
둘째 줄에 $N$개 컨테이너 각각의 무게가 주어집니다.
둘째 줄에 $N$개 컨테이너 각각의 무게가 주어집니다.
출력 설명
순서대로 $M$대의 트럭에 나누어 실을 때, 한 트럭이 감당해야 하는 최대 무게의 최솟값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
10 20 30 40 50
출력 예시
COPY
복사되었습니다!
복사되었습니다!
60도움
이분탐색 범위: 하한은 컨테이너 최대 무게, 상한은 모든 무게의 합입니다. 검사 함수: 최대 적재 무게 $c$로 앞에서부터 누적하다 초과하면 새 트럭을 사용하며, 총 트럭 수가 $M$ 이하인지 확인합니다.