力扣1011题：二分查找解法详解

一、题目解读

力扣1011题是一个经典的运载能力优化问题。题目要求我们找到传送带的最小运载能力，使得所有包裹在D天内能够被运送完毕。这个问题可以抽象为一个典型的二分查找应用场景，通过确定运载能力的上下界，逐步缩小范围找到最优解。

二、解题思路

1. 问题分析：我们需要找到一个最小的运载能力值，使得按顺序装载包裹时，总天数不超过D

2. 二分查找适用性：运载能力存在明确的下界(单个最大包裹重量)和上界(所有包裹总重量)

3. 贪心验证：对于给定的运载能力，使用贪心算法计算实际需要的运输天数

4. 边界调整：根据计算天数与目标天数的比较，调整二分查找的边界

三、解题步骤

1. 初始化二分查找的左右边界：left为最大单件重量，right为总重量

2. 进入循环，计算中间值mid作为当前尝试的运载能力

3. 模拟运输过程，计算在当前运载能力下需要的实际天数

4. 比较实际天数与目标天数：

• 若实际天数≤D，说明运载能力可能过大，尝试缩小右边界

• 若实际天数>D，说明运载能力不足，需要增大左边界

5. 当left==right时，找到最小运载能力

四、完整代码与注释

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        // 确定二分查找的左右边界
        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 current = 0; // 当前运载量
            int need = 1;    // 需要的天数
            
            // 计算当前运载能力下需要的天数
            for (int w : weights) {
                if (current + w > mid) {
                    need++;
                    current = 0;
                }
                current += w;
            }
            
            // 调整二分查找边界
            if (need <= days) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

五、总结

本题展示了二分查找算法在实际问题中的巧妙应用。通过合理确定搜索边界和验证函数，我们能够高效地找到最优解。该解法时间复杂度为O(n log sum)，其中n为包裹数量，sum为总重量，空间复杂度为O(1)，是一种非常高效的解决方案。