【每日一题】1011. 在 D 天内送达包裹的能力

https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/

思路：
分析题目有两个临界值，容量足够，能够送达；容量不够，不能送达。我们要找的那个容量是满足条件的最小容量，可以考虑使用二分法。

/**
 * 切分成 D 段，求满足条件的最小容量
 * 这道题有两个临界值，最小值是物品中的最大重量。最小值是所有物品重量的和
 * 可以考虑使用二分法，逐渐逼近正确值
 */

class Solution {
    public int shipWithinDays(int[] weights, int D) {
        int left = Integer.MIN_VALUE, right = 0;
        for(int w : weights){
            left = Math.max(left, w);
            right += w;
        }

        while(left < right){
            //mid 就是我们进行试探的值
            int mid = (left + right) / 2;
            //下面就是一个判断条件
            int need = 0;//需要的运输次数
            int cur = 0;
            for(int i = 0; i < weights.length; i++){
                //已经超出了最大运载能力
                if(cur + weights[i] > mid){
                    need ++;
                    cur = 0;
                }
                cur += weights[i];
            }
            //当前的 mid 满足条件，说明我们的运载能力是足够的
            if(need < D){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return left;
    }
}