题目描述（中等难度）

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

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

示例 1：

  1. 输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
  2. 输出：15
  3. 解释：
  4. 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
  5. 第 1 天：1, 2, 3, 4, 5
  6. 第 2 天：6, 7
  7. 第 3 天：8
  8. 第 4 天：9
  9. 第 5 天：10
  11. 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：

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

示例 3：

输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

解法一：二分法

思路：

分析题干，按给出重量的顺序往传送带上装载包裹，装载的重量不会超过船的最大运载重量，也就是说船的最低运载能力不小于数组中的最大值(最差的情况也可以装载一个,这一个可能是货物中的任意一个，所以要取其中的最大重量)，最高运载能力不大于数组总和(避免一天就运完)。所以它取值最后的区间应该是【max[weights]，sum[weights]】。
有了这个思路之后，我们只要取出这两个端点值，然后再使用二分查找法，找出那个能满足送达包裹的最小值即可。
然后是，我们去试值，难点在于 如何判断这个值能不能满足在D天内送完包裹。

//判断最低运载能力为H的时候能否在D天内送达
    public boolean verification(int[] weights, int D, int H){
        //初始化天数=1
        int count = 1;
        //每天运送的包裹的总量
        int singleWeight = 0;
        for (int i = 0; i < weights.length; i++) {
            //累计包裹总量
            singleWeight+=weights[i];
            //如果累计包裹总量singleWeight > H，天数+1
            if (singleWeight>H){
                count++;
                singleWeight = weights[i];
            }
            //如果当前累计的天数count > D，说明当前H不满足条件，返回false
            if (count>D){
                return false;
            }
        }
        //说明当前H满足条件，返回true
        return true;
    }

    /**
     * 首先，我们可以明确最低运载能力必须要不小于数组中的最大值（必须要满足一天至少运一个，
     * 运载能力至少要比每个包裹的重量都要大才行，不然就会出现有包裹一直运不走），
     * 不大于数组的总和（一天全部运走），即区间[max(weights), sum(weights)];
     * @param weights
     * @param D
     * @return
     */
    //二分法查找满足条件中的最小值
    public int shipWithinDays(int[] weights, int D) {
        //二分查找 r = 数组的总和， l = 数组的最大值
        int r = Arrays.stream(weights).sum();
        int l = Arrays.stream(weights).max().getAsInt();
        //l < r
        while (l<r){
            int mid = (l+r)/2;
            //如果mid满足verification，则逼近右指针
            if (verification(weights,D,mid)){
                //包括mid
                //右指针是满足条件的
                r = mid;
            }else {
                //逼近左指针，mid + 1
                //左指针左边的数(包括左指针)都不满足条件，所以直接+1，跳过了左指针
                l = mid+1;
            }
        }
        //返回当前l就是最小的满足条件的值，即最低运载能力
        return l;
    }