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

为保证权益，题目请参考 1011. 在 D 天内送达包裹的能力(From LeetCode).

解决方案1

CPP

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;

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) / 2;
            // need 为需要运送的天数
            // cur 为当前这一天已经运送的包裹重量之和
            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;
    }
};

int main()
{
    return 0;
}