LeetCode 1011 Capacity To Ship Packages Within D Days

    
        标签：
        
            二分搜索
        
            LeetCode
        
    发布于：2022-02-03 17:58:17
    编辑于：2022-02-05 16:56:07
    浏览量：1193

题目分析

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

这道题与 LeetCode 875 Koko Eating Bananas 非常类似，区别在于这里的货物是整件的。

注意这里装货的次序是固定的。

迭代法

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int l = *max_element(weights.begin(), weights.end());
        int r = accumulate(weights.begin(), weights.end(), 0);
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (isOkay(weights, days, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
    
    bool isOkay(vector<int>& weights, int days, int c) {
        int d = 1;
        int rest = c;
        for (int i = 0; i < weights.size(); i++) {
            if (rest >= weights[i]) {
                rest -= weights[i];
            } else {
                d++;
                rest = c;
                rest -= weights[i];
            }
        }
        return d <= days;
    }
};

Links: leetcode-1011-capacity-to-ship-packages-within-d-days