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

很好的题，一开始想dfs爆搜的，还是直接看了三叶学姐的题解。
是一道二分查找的题，我们要找的是能在D天内送完的最小载重量。不考虑天数的情况下最小的载重量是足够运送最大货物的，最大载重量就是所有货物一天运完。
左边界就是max，有边界就是sum，对其进行二分，写一个check函数，这个很重要，对当前运力进行判断，这是我们二分缩小搜索范围的标准。check内部就是计算当前运力需要几天运完
如果运送天数<=D，mid不能扔，继续去左边找，看看能否找到更小的。如果>D，就要提升载重量，去右边找，而且mid不要了。
最后返回的r，因为我们控制<=的时候mid不丢弃变成r，当结束时，r是那个最小的解

class Solution {
    
public:
    bool check(vector<int>& weights,int t,int D){
    
        int day = 0;
        for(int i = 0; i < weights.size();){
    
            day++;
            int sum = 0;
            //没越界且没超过载重的情况下，可以运送
            while(i < weights.size() && sum + weights[i] <= t){
    
                sum += weights[i++];
            }
        }
        return day  <= D;
    }
    int shipWithinDays(vector<int>& weights, int D) {
    
        //从最小运力和最大运力之间用二分找出运D天的
        //如果当前运力运送的超过D天就去右边，小于等于去左边。为什么小于等于
        //最后返回r，为什么
        int l = 0, r = 0;
        for(int x : weights){
    
            l = max(l,x);
            r += x;
        }
        while(l < r){
    
            int mid = l + (r-l)/2;
            if(check(weights,mid,D)){
    
                r = mid;
            }
            else{
    
                l = mid + 1;
            }
        }
        //因为我们控制<=的时候mid不丢弃变成r，当结束时，r是那个最小的解
        return r;
    }
};