leetcode:在 D 天内送达包裹的能力

古城微笑少年丶 2023-01-17 03:27 46阅读 0赞

链接：[https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/][https_leetcode-cn.com_problems_capacity-to-ship-packages-within-d-days]

我是按照这个思路来做的。

如果随便给一个船的运载重量，判断一下在D天内能否运完货物？

代码如下

/**
     * nums 货物
     * power 船的运载重量
     * D 给定的天数
     */
    private boolean check(int[] nums, int power, int D) {
        // count表示船的运载能力为power时，运完所有货物需要的天数
        // 注意count的初始值和返回值的对应关系 
        int count = 1, cap = power;
        for (int num : nums) {
            // 船剩下的运载量小于num货物的重量，需要放到下一天去运
            if (num > cap) {
                count++;
                cap = power;
            }
    
            cap -= num;
        }
    
        return count <= D;
    }

有了这个函数好办了。剩下的我们只需要确定一下在题目给的条件下，船可能的最大运载量和最小运载量，然后使用**二分查找**不断逼近最小值即可。

*  由于货物不可分割，那么至少每天需要运一个货物，可知**船最小的运载量就是最重的那个货物的重量**。
 *  假设所有货物一天运完，可知**船最大的运载量是所有货物重量之和**。

确定了这两个数，就好办了，请看代码。

class Solution {
        public int shipWithinDays(int[] weights, int D) {
            // max表示不考虑其他因素，船的最低运载能力，即一天运一个货物，此时最低运载能力就是所有货物里最重的
            // sum为货物的总重量，也是船的最大运载能力，即一天运完所有货物
            int max = 0, sum = 0;
            for (int weight : weights) {
                max = Math.max(max, weight);
                sum += weight;
            }
    
            int left = max, right = sum;
            // 二分查找，不断查找直到找到在D天内能运完所有货物的最低运载能力
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (check(weights, mid, D)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
    
            return right;
        }
    
        /**
         * nums 货物
         * power 船的运载重量
         * D 给定的天数
         */
        private boolean check(int[] nums, int power, int D) {
            // count表示船的运载能力为power时，运完所有货物需要的天数
            // 注意count的初始值和返回值的对于关系 
            int count = 1, cap = power;
            for (int num : nums) {
                // 船剩下的运载量小于num货物的重量，需要放到下一天去运
                if (num > cap) {
                    count++;
                    cap = power;
                }
    
                cap -= num;
            }
            
            return count <= D;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70_pic_center]

[https_leetcode-cn.com_problems_capacity-to-ship-packages-within-d-days]: https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/9badf84a8c824dffade381bf4b123183.png