跳转至

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

思路

感觉本题难度在函数f身上,要计算多少天能运完,需要考虑到以下情况: - 一天不一定能完整运完,可能会剩下运载重量没用完,因此需要判断cap >= weights[i] - 有可能一天就可以运完,因此需要循环跳出break

class Solution {
public:
    int f(vector<int>& weights, int x){
        int days = 0;
        int i = 0;
        while(i < weights.size()){
            int cap = x;
            while(i < weights.size()){
                if(cap >= weights[i]){
                    cap -= weights[i];
                    i++;
                }else{
                    break;
                }
            }
            days++;
        }
        return days;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        int left = 0, right = 0;
        for(int weight: weights){
            left = max(left, weight);
            right += weight;
        }
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(f(weights, mid) == days){
                right = mid - 1;
            }else if(f(weights, mid) < days){
                right = mid - 1;
            }else if(f(weights, mid) > days){
                left = mid + 1;
            }
        }
        return left;
    }
};