力扣1011. 在 D 天内送达包裹的能力C++

• 题目链接
• • 思路分析
  • • 解题代码

题目链接

在 D 天内送达包裹的能力

思路分析

对于这道题目，我们首先想到的第一种办法就是，我们的最大运载能力是所有包裹重量的和，那么最低运载能力就是1
因此我们就可以使用便利的方法进行统计，统计出我们能满足D天内将所有货物搬运的最低运载能力
对于运载能力进行考虑时，当我们想通过遍历进行处理时，当我们当前的重量和大于我们给出的最低运载能力时， 就说明一趟不能装完，因此在给出最低运载能力的条件下，我们运载天数需要+1，最后和D进行比较，如果小于D则说明我们已经找到了满足条件的最低运载能力
接下来我们在穷举遍历的基础上考虑更加有效的算法，当你明白了穷举算法的思路之后，我们可以回过头看遍历的顺序，就是从1-包裹的累计和我们可以认为这是一个有序的数组，因此我们可以在这一基础上考虑使用二分的技术，来进一步减少搜索时间，当我们所找到一个运载能力之后，说明我们所要求解的最终结果一定是在我们找到的这个运载能力的左侧，如果不满足，则一定是在右侧出现，请读者结合代码对照思路进行理解，作者在代码中加入了详细的注释

解题代码

class Solution {
public:
    bool check(vector<int>& weights, int mid , int D)
    {
        int cnt = 1, cur = 0;
        for(int& weight : weights)
        {
            //如果当前值加上重量大于mid值
            //说明我们一天一趟装不上，要对cnt++，所以要将cnt初始化为1 
            //必须要保证我们运载能力大于等于包裹中任意一个的重量，必然为false
            if (mid < weight)
                return false;
            if(cur + weight > mid)
            {
                ++cnt;
                cur = 0;
            }
            cur += weight;
        }
        return cnt <= D;
    }
    int shipWithinDays(vector<int>& weights, int D) {
        //考虑使用二分的方法进行解决
        //船的最大运载能力是整个 传送带上的所有包裹的重量之和
        //那么最低运载能力就是1
        //因此我们左右边界就是 [1, sum]
        int right = 0;
        int left  = 1;
        int ans = right;
        for(int& weight  : weights)
        {
            right += weight;
        }
        while(left <= right)
        {
            //检查中间值是否合适
            int mid = left + (right-left)/2;
            if(check(weights, mid, D))
            {
                //说明这个可以
                //我们要缩小范围，缩小右边界
                right = mid - 1;
                ans = mid;
            }
            else
            {
                left = mid+1;
            }
        }
        return ans;
    }
};```