题目

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

解法

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int low=0;
        int high=0;
        for(auto num:weights){
            low=max(low,num);
            high+=num;
        }
        while(low<high){
            int cap=low+(high-low)/2;
            int temp=0;
            int day=1;
            for(int i=0;i<weights.size();i++){
                temp+=weights[i];
                if(temp>cap){
                    day++;
                    temp=weights[i];
                }
            }
            //运送的天数大于要求天数，说明运载能力猜小了
            if(day>days){
                low=cap+1;
            }else{
                high=cap;
            }
        }
        return low;
    }
};

二分查找做多了感觉套路都差不多