在 D 天内送达包裹的能力

怎样从“weights 分 d 天运完,最小船载重 capacity。”推导出 二分答案 · 船运，并证明每次状态变化都不会漏掉答案？

中心结论：二分 capacity,贪心看需几天(超则天+1)。

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

1 <= D <= weights.length <= 50000 1 <= weights[i] <= 500

在本站主例中，weights 分 d 天运完,最小船载重 capacity。

算法最终需要得到或观察：最小 capacity。

枚举每一个可能答案会做大量相似验证；可行性单调时，可以直接在答案空间二分。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“答案可行性刻度”，明确答案需要观察什么。
2. 2状态只维护 lo/hi capacity、days 验证。
3. 3转移每一步按照 二分 capacity,贪心看需几天(超则天+1)。
4. 4收尾读取 最小 capacity。，并复核边界与复杂度。

先证明答案越大或越小时，可行性只朝一个方向变化。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：lo/hi capacity、days 验证。

给出一个数组和天数 D，要求正好在 D 天把数组中的货物都运完。求传输带上能承受的最小货物重量是多少。 这一题和第 410 题完全一样，只不过换了一个题面。代码完全不变。思路解析见第 410 题。

二分 capacity,贪心看需几天(超则天+1)。

执行过程中持续维护：lo/hi capacity、days 验证。

正确性依赖以下不变量：验证随 capacity 增大 days 减少。

面试时可以压缩为：二分+贪心 O(n log sum)。

落到当前题，执行机制可以压缩为：二分 capacity,贪心看需几天(超则天+1)。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入weights 分 d 天运完,最小船载重 capacity。 因为：二分 capacity,贪心看需几天(超则天+1)。
2. 2二分船载容量 cap答案二分模板。 因为：与 split array 同型。
3. 3cap=21 可在 5 天内运完贪心模拟装船天数。 因为：单日超载则开新 day。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5cap=15 可在 5 天内运完贪心模拟装船天数。 因为：单日超载则开新 day。
6. 6cap=12 不够贪心模拟装船天数。 因为：单日超载则开新 day。
7. 7最小容量 = 15返回最小可行 cap。 因为：O(n log sum)。
8. 8收尾与复杂度最小 capacity。 因为：时间 O(n) · 空间 O(1)。二分 capacity,贪心看需几天(超则天+1)。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func shipWithinDays(weights []int, D int) int {
	maxNum, sum := 0, 0
	for _, num := range weights {
		sum += num
		if num > maxNum {
			maxNum = num
		}
	}
	if D == 1 {
		return sum
	}
	low, high := maxNum, sum
	for low < high {
		mid := low + (high-low)>>1
		if calSum(mid, D, weights) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func calSum(mid, m int, nums []int) bool {
	sum, count := 0, 0
	for _, v := range nums {
		sum += v
		if sum > mid {
			sum = v
			count++
			// 分成 m 块，只需要插桩 m -1 个
			if count > m-1 {
				return false
			}
		}
	}
	return true
}

func main() {
    // 1. 主例
    //    输入：mode="ship-packages", weights=[1,2,3,4,5,6,7,8,9,10], days=5
    //    期望：最小 capacity。
    //
    // 2. 失败 / 未命中
    //    检查：贪心装船:当前超重开新的一天。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC875；LC410
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意weights 分 d 天运完,最小船载重 capacity。
2. 2重复枚举每一个可能答案会做大量相似验证；可行性单调时，可以直接在答案空间二分。
3. 3优化二分 capacity,贪心看需几天(超则天+1)。
4. 4证明验证随 capacity 增大 days 减少。
5. 5复杂度时间 O(n)，空间 O(1)