企业官网建设流程全解析

问题解析：力扣1011 题 “在 D 天内送达包裹的能力” 要求确定在给定天数D内，将所有包裹从传送带上运完的最低运载能力。运载能力capacity表示船每天能运送的最大重量，且必须按数组顺序运送，每天运送的总重量不能超过capacity。

核心思路：这是一个二分查找问题。运载能力capacity存在一个可行域：

• 下界left：至少需要能运走最重的单个包裹，即max(weights)。
• 上界right：最坏情况一天运完所有包裹，即sum(weights)。
  在[left, right]范围内，对于任意一个capacity，我们可以通过模拟运送过程计算出所需天数needDays。根据needDays与D的关系来调整二分查找的边界：
  *若needDays <= D，说明当前运力充足或刚好，可以尝试减小运力（缩小右边界）。
• 若needDays > D，说明当前运力不足，必须增大运力（增大左边界）。
  最终，left即为所求的最小运力。

C++ 代码实现：

class Solution { public: int shipWithinDays(vector<int>& weights, int D) { // 确定二分查找的左右边界 int left = *max_element(weights.begin(), weights.end()); // 运力至少能装下最重的包裹 int right = accumulate(weights.begin(), weights.end(), 0); // 运力最多一天运完所有 while (left < right) { int mid = left + (right - left) / 2; // 当前尝试的运力 int need = 1; // 需要运送的天数，初始为1天 int cur = 0; // 当前这一天已经装载的重量 // 模拟以 mid 为运力，运送所有包裹所需的天数 for (int weight : weights) { if (cur + weight > mid) { // 如果加上当前包裹会超载 ++need; // 则需要新的一天 cur = weight; // 新的一天从当前包裹开始装 } else { cur += weight; // 没超载，继续装 } } // 根据所需天数调整二分边界 if (need <= D) { right = mid; // 运力足够或有余，尝试更小的运力 } else { left = mid + 1; // 运力不足，必须增大 } } return left; // 此时 left == right，即为最小运力 } };

代码说明：

1. 边界初始化：left初始化为数组最大值，right初始化为数组总和 。
2. 二分查找循环：当left < right时，计算中间值mid作为尝试的运力。
3. 模拟运送函数（内嵌循环）：遍历所有包裹，累加当前天的重量cur。若加上当前包裹后重量超过mid，则天数need加一，并在新的一天开始运送该包裹 。
4. 边界调整：
   • 若计算出的所需天数need小于等于D，说明运力mid可行，为了寻找最小运力，将搜索范围缩小至左半部分 (right = mid)。
   • 若need大于D，说明运力mid不足，需增大运力，将搜索范围调整至右半部分 (left = mid + 1)。
5. 返回值：循环结束时left和right相等，即为满足条件的最小运力。
6. 复杂度分析：
   • 时间复杂度：O(n log m)，其中n是包裹数量，m是包裹总重量。二分查找复杂度为 O(log m)，每次模拟运送需要 O(n)。
   • 空间复杂度：O(1)，只使用了常数个额外变量。

示例：
输入：weights = [1,2,3,4,5,6,7,8,9,10],D = 5

1. left = 10,right = 55。
2. 第一次尝试mid = (10+55)/2 = 32，模拟运送：[1,2,3,4,5,6,7,8](36>32，分两天)，[9,10]，共需3天 (need=3)。3 <= 5，所以right = 32。
3. 继续二分，最终找到最小运力为15。验证：以运力15运送，[1,2,3,4,5],[6,7],[8],[9],[10]正好需要5天。

参考来源

• LeetCode1011
• ❤️67❤️带新手一起刷力扣 (LeetCode)❤️代码有详细的注释❤️反思总结❤️67. 二进制求和
• 力扣67-二进制求和-C++
• Leetcode 693. 交替位二进制数 C++
• Leetcode 67. 二进制求和 C++