1011. 在 D 天内送达包裹的能力
题目描述
输入数组 weights 和整数 days。传送带上第 i 个包裹重 weights[i]，所有包裹要在 days 天内用一艘船运走。
船每天装一次货，必须按 weights 中的先后顺序装，每天装的是接着前一天往后的一段连续包裹。当天装上的总重量不能超过船的运载能力。
返回能在 days 天内运完全部包裹的最小运载能力。
示例 1
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5 输出：15
解释：能力为 15 时可分成 [1..5]、[6,7]、[8]、[9]、[10] 五天；不能打乱顺序去凑 14。
示例 2
输入：weights = [3,2,2,4,1,4], days = 3 输出：6
解释：按 [3,2]、[2,4]、[1,4] 分三天，每天不超过 6。
示例 3
输入：weights = [1,2,3,1,1], days = 4 输出：3
解释：按 [1]、[2]、[3]、[1,1] 分四天，最大一天是 3。
数据范围
1 <= days <= weights.length <= 5 * 10^41 <= weights[i] <= 500
解题思路
运载能力越大，需要的天数越少，具有单调性。答案范围是 [max(weights), sum(weights)]。对能力 mid 贪心模拟：能装就装，装不下就换下一天，得到所需天数 need。need ≤ days 则 hi = mid，否则 lo = mid + 1。
为什么正确
最低可行能力始终在 [lo, hi] 中；hi 总是可行的。
复杂度分析
时间 O(n log S)，S = sum(weights)；空间 O(1)。
易错点
下界必须是 max(weights)，否则最重的包裹永远装不上，贪心会出错；need 从 1 开始计数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
need, load = 1, 0
for w in weights:
if load + w > mid:
need += 1
load = 0
load += w
if need <= days:
hi = mid
else:
lo = mid + 1
return loclass Solution {
public int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0; for (int w : weights) { lo = Math.max(lo, w); hi += w; }
while (lo < hi) {
int mid = (lo + hi) / 2;
int need = 1, load = 0;
for (int w : weights) {
if (load + w > mid) {
need++;
load = 0;
}
load += w;
}
if (need <= days) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int lo = *max_element(weights.begin(), weights.end()), hi = accumulate(weights.begin(), weights.end(), 0);
while (lo < hi) {
int mid = (lo + hi) / 2;
int need = 1, load = 0;
for (int w : weights) {
if (load + w > mid) {
need++;
load = 0;
}
load += w;
}
if (need <= days) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
};func shipWithinDays(weights []int, days int) int {
lo, hi := 0, 0
for _, w := range weights { if w > lo { lo = w }; hi += w }
for lo < hi {
mid := (lo + hi) / 2
need, load := 1, 0
for _, w := range weights {
if load+w > mid {
need++
load = 0
}
load += w
}
if need <= days {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}var shipWithinDays = function(weights, days) {
let lo = Math.max(...weights), hi = weights.reduce((s, w) => s + w, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
let need = 1, load = 0;
for (const w of weights) {
if (load + w > mid) {
need++;
load = 0;
}
load += w;
}
if (need <= days) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};function shipWithinDays(weights: number[], days: number): number {
let lo = Math.max(...weights), hi = weights.reduce((s, w) => s + w, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
let need = 1, load = 0;
for (const w of weights) {
if (load + w > mid) {
need++;
load = 0;
}
load += w;
}
if (need <= days) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}