D天内送达包裹的能力

0x1 题目详情

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。weight不保证有序。

测试用例

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5 输出：15 解释： 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示： 第 1 天：1, 2, 3, 4, 5 第 2 天：6, 7 第 3 天：8 第 4 天：9 第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

0x2 解题思路

我在看道题时没有什么思路，是看了题解之后再做出来的。不过这道题是用二分求出来的我是没想到(ps:怎么什么都想不到...).。废话完了，来看看题怎么解。

这道题要求运载能力尽可能小，但小也不是没限制的，需要指定的天数运送完货物。

那么一艘船的最大运载能力和最小运载能力我们是一定可以求出来的。最小运载能力及船中最小的货物(因为最小重量不可分);而最大运载能力即一把梭哈，一次全给它运完。

那么我们就需要在运载能力区间[min,max]找到一个运载能力，在天数拉满的情况给它运完(不然怎么最小呢)。

ok，题目轮廓已经清晰了，即在一个有序数组内找到一个符合条件的数。求解这种问题肯定是二分法最快啦。

最后还需要说明:我们需要额外封装一个方法在运载能力给定的情况下，求出需要的天数。

0x3 代码实现

二分法这里采用的是左闭右开的区间，如果不了解这个左闭右开区间有啥好处的同学，可以去看我写的关于二分法的使用总结。

时间复杂度为$O(N)$，因为在最开始遍历了一遍数组。

class Solution {
    public int shipWithinDays(int[] weights, int D) {
        if(weights== null || weights.length==0){
            return 0;
        }
        int max=0;//最高运载能力也就是数组元素的总和
        int min=0;//最低运载能力也就是数组中单个重量最大的
        for(var elem:weights){
            max+=elem;
            min=Math.max(elem,min);
        }
        max+=1;
        //在最低和最高运载能力中进行二分
        while(min<max){
            int mid=min+(max-min)/2;
            int days=calcDates(weights,mid);
            //运载能力太小了
            if(days>D){
                min=mid+1;
            }
            //运载能力太大了
            else{
                max=mid;
            }
        }
        //最后终止循环时，max一定指向的是符合条件的数
        return max;
    }
    int calcDates(int[] weights,int capacity){
        int result=0;
        int max=0;
        for(int i=0;i<weights.length;i++){
            if(max+weights[i]>capacity){
                result++;
                max=0;
            }
            max+=weights[i];
        }
        return ++result;
    }
}

0x4 课后总结

关于什么时候使用二分法呢？我上面已经给出了总结：

1. 在一个有序数组寻找某一个符合特定条件的数，这样的问题使用二分法肯定是最快的。但是要注意：使用二分一般都需要保证元素有序哦，当然一些特殊的问题也可以使用二分的思想来做。

2. 或者我们想要查找一个值，且知道这个值的范围，那么我们就可以通过一些条件不断排序一些不可能包含答案的范围，最后二分完了以后，只需要查看我们找到的值是否符合要求即可。

总的来说，只要我们知道要查找的值的范围，然后就可以尝试通过二分法结合一些已知条件求解答案。