1011. Ability to deliver packages within D days

Good question , At first I thought dfs Explosive search , Or I read the solution of sister Sanye directly .
It's a binary search problem , What we are looking for is to be able to D The minimum carrying capacity delivered within days . Without considering the number of days, the minimum load is enough to transport the largest goods , The maximum carrying capacity is that all goods are transported in one day .
The left border is max, There are boundaries sum, Split it in two , Write a check function , This is very important , Judge the current transportation capacity , This is our standard to narrow the search scope .check Internally, it is calculated that the current transportation capacity will take several days to complete
If the delivery days <=D,mid Can't throw , Continue to look on the left , See if you can find something smaller . If >D, It is necessary to increase the load , Go to the right , and mid No more .
Last returned r, Because we control <= When mid Do not discard into r, When it's over ,r Is the smallest solution

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;
            // Without crossing the boundary and exceeding the load , It can deliver 
            while(i < weights.size() && sum + weights[i] <= t){
    
                sum += weights[i++];
            }
        }
        return day  <= D;
    }
    int shipWithinDays(vector<int>& weights, int D) {
    
        // Use two points to find the transportation between the minimum transportation capacity and the maximum transportation capacity D Days of 
        // If the current transportation capacity exceeds D Days go to the right , Less than or equal to the left . Why is it less than or equal to 
        // Finally back to r, Why? 
        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;
            }
        }
        // Because we control <= When mid Do not discard into r, When it's over ,r Is the smallest solution 
        return r;
    }
};