1011. Capacity To Ship Packages Within D Days¶
题目信息¶
- 题号:
1011
- 难度:
Medium
- 主题:
顺序装载、每日容量、最小可行值
- 原题:
- 重点:
包裹必须按数组顺序装船且不能拆分;每天装载连续的一段,要求在不超过
days天内运完并最小化固定日容量
题目重述¶
传送带上的包裹按 weights 中的顺序等待运输,weights[i] 是第 i 个包裹的重量。船每天从尚未运输的第一个包裹开始依次装载,不能跳过、重排或拆分包裹;当天总重量不能超过船的固定容量。
给定允许的最大运输天数 days,请返回能够在不超过 days 天内运完全部包裹的最小船容量。每天可以运输一个或多个包裹,但容量至少要容纳最重的单个包裹。
1 <= weights.length <= 5 * 10^4,1 <= weights[i] <= 500,1 <= days <= weights.length。
自建示例¶
容量过小会多用一天:
输入:weights = [3,2,2,4,1], days = 3
输出:5
解释:容量 5 时三天可分别运输 [3,2]、[2]、[4,1]。容量 4 时至少需要四天,因此最小容量为 5。
必须在一天内全部运完:
输入:weights = [2,5,1], days = 1
输出:8
解释:只有一天可用,船必须一次装下全部包裹,因此最小容量等于总重量 8。