LeetCode1011(2021.4.26)

LC1011. 在 D 天内送达包裹的能力

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int left = *max_element(weights.begin(), weights.end()), right = accumulate(weights.begin(), weights.end(), 0);
        while (left < right) {
            int mid = left + right >> 1;
            int need = 1, cur = 0;
            for (int weight: weights) {
                if (cur + weight > mid) {
                    need++;
                    cur = 0;
                }
                cur += weight;
            }
            if (need <= D) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};

发表评论