[1011] 在 D 天内送达包裹的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
示例 2：
输入：weights = [3,2,2,4,1,4], days = 3
输出：6
示例 3：
输入：weights = [1,2,3,1,1], days = 4
输出：3

这道题是一道非常经典的「二分搜索答案」类型的题目。题目问的是最低运载能力，而运载能力的取值范围是有明确上下界的，并且具有单调性——运载能力越大，所需天数越少。因此可以对答案进行二分。

首先确定二分的搜索范围：

下界：运载能力至少要能装下最重的那个包裹，即 max(weights)，否则这个包裹永远无法运出。
上界：一次性把所有包裹运完，即 sum(weights)。

确定了搜索区间后，对于每一个候选的运载能力 target，我们贪心地模拟装载过程：按顺序往船上装包裹，当前一天装不下时就开启新的一天。如果总天数超过了 days，说明 target 太小，需要增大；否则说明 target 可行，但可能还有更小的可行值，继续向左收缩。

这正是一个标准的「搜索左边界」的二分。

function shipWithinDays(weights: number[], days: number): number {
  let l = Math.max(...weights);
  let r = weights.reduce((sum, cur) => sum + cur, 0);

  while (l < r) {
    const target = (l + r) >> 1;
    let flag = true;

    let nowDay = 1;
    let nowLoad = 0;
    for (let weight of weights) {
      if (nowLoad + weight > target) {
        // 当前这一天装不下了，开启新的一天
        nowLoad = 0;
        nowDay += 1;
        if (nowDay > days) {
          // 用的时间太长了，方案不行，需要用更大的装载量
          flag = false;
          break;
        }
      }
      nowLoad += weight;
    }

    if (flag) {
      // 方案可行，但看看有没有装载量更小的方案也可行
      r = target;
    } else {
      l = target + 1;
    }
  }
  return r;
}

整体思路总结：

确定搜索区间 [max(weights), sum(weights)]。
二分取中间值 target，贪心模拟判断 target 是否能在 days 天内完成运输。
可行则收缩右边界，不可行则收缩左边界。
最终 l === r 时即为最低运载能力。

时间复杂度为 O(n · log(sum - max))，其中 n 为包裹数量。

[1011] 在 D 天内送达包裹的能力 ​

[1011] 在 D 天内送达包裹的能力