力扣1011题详解：船只装载问题的二分查找优化解法（C++代码实现）

一、题目解读

力扣1011题要求在给定的货物重量数组中，计算船只每天最多装载一定重量时，最少需要多少天完成运输。题目关键在于找到满足天数限制的最小最大载重量，属于典型的查找最值问题。

二、解题思路

采用二分查找算法。核心思想是将问题转化为：是否存在一个载重量阈值，使得按该阈值分配货物时，所需天数不超过给定天数。通过二分查找该阈值，降低时间复杂度。

三、解题步骤

1. 确定二分边界：左边界为最大货物重量（单日至少载1件），右边界为总重量（单日载完）；

2. 二分查找：每次计算中间值mid对应的所需天数；

3. 模拟装载：遍历货物，若当前累计重量超mid，天数递增并重置累计；

4. 调整边界：若天数≤给定天数，说明阈值可能更小（右移），否则需更大（左移）；

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;
    }
};

注释解析：

● left/right初始化为合理边界，避免无效查找；

● 内部循环通过模拟装载判断mid可行性；

● 时间复杂度O(nlogsum)，n为货物数，sum为总重量。

五、总结

本题通过将“求最小满足条件值”转化为二分查找，巧妙利用单调性优化。关键在于设计合理的二分判定条件（模拟装载过程），以及边界值的正确初始化。掌握此类转换思路可高效解决类似最值查找问题。