1011_CapacityToShipPackagesWithinDDays - a920604a/leetcode GitHub Wiki

class Solution {
public:
    int cost(vector<int>& weights, int cap){
        int n = weights.size(), days = 0;
        for(int i=0;i<n;){
            int c = cap;
            while(i<n && c>=weights[i]){
                c-=weights[i++];
            }
            days++;
        }
        return days;
        
    }
    int shipWithinDays(vector<int>& weights, int days) {
        
        int l = 1, r=0;
        for(int w:weights){
            l = max(w,l);
            r+=w;
        }
        
        while(l<r){
            int cap = l + (r-l)/2;
            cout<<l<<" "<<r<<endl;
            // 運送能力 cap 下需要 evalday 才可以運送完
            int evalday = cost(weights, cap);
            // 減少運送能力，看是否還能運送完，因為題目要求最低運送能力
            if(evalday == days) r = cap;
            // 花太多天，運送太慢，加快速度 
            else if(evalday > days) l = cap +1;
            // 花太少天，運送太快，放慢速度
            else if(evalday < days) r = cap;
        }
        return l;
    }
};