当前位置：首页 > news >正文

二分查找解力扣1011最优运载能力

news 2026/7/8 16:14:06

问题解析：力扣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，即为最小运力 } };

代码说明：

边界初始化：left初始化为数组最大值，right初始化为数组总和。
二分查找循环：当left < right时，计算中间值mid作为尝试的运力。
模拟运送函数（内嵌循环）：遍历所有包裹，累加当前天的重量cur。若加上当前包裹后重量超过mid，则天数need加一，并在新的一天开始运送该包裹。
边界调整：
- 若计算出的所需天数need小于等于D，说明运力mid可行，为了寻找最小运力，将搜索范围缩小至左半部分 (right = mid)。
- 若need大于D，说明运力mid不足，需增大运力，将搜索范围调整至右半部分 (left = mid + 1)。
返回值：循环结束时left和right相等，即为满足条件的最小运力。
复杂度分析：
- 时间复杂度：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

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