[leetcode] 1014. Capacity To Ship Packages Within D Days : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

Capacity To Ship Packages Within D Days.cpp

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        // find minimum weights can Answer
        int l = 0;
        int r = 0;
        for(int i=0;i<weights.size();i++){
            int nowWeight = weights[i];
            l = max(l, nowWeight);
            r += nowWeight;
        }
        
        int answer = 0;
        while(l < r){
            int maxSum = (l + r) / 2;
            if(getDays(weights, maxSum) <= D) {// possible
                r = maxSum;
            }
            else // impossible
                l = maxSum + 1;
        }
        return r;
    }
    
    int getDays(vector<int> weights, int max){
        int subSum = 0, day = 1;
        for(int i=0;i<weights.size();i++){
            int nowWeight = weights[i];
            int nextSubSum = subSum + nowWeight;
            if(max < nextSubSum ){ // impossible
                day++;
                subSum = nowWeight;
            }else{
                subSum = nextSubSum;
            }
        }
        return day;
    }
};