题目描述

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

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

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

数值范围

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

样例

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 

算法1

(二分法) $O(nlog10^8)$

初始想法是组合题，示例中是必须要按顺序装货物，其实思路是相似的，都是搜索解空间，从而找到最优解，而搜索的方法最优是二分，所以归根到底是二分搜索，而且是整数二分；
需要注意的点就是二分的写法，题目要求的是最低运载要求，所以需要是保留右端点，当 middle 满足要求时搜索 left ~ middle。
最大值选为货物总重量，最大为 50000 * 500，故搜索的复杂度是 $O(log10^8)$，每次都需要遍历货物来看是否满足，所以整个算法的复杂度为 $O(nlog10^8) \approx 10^6$
这里的 left 可以选择数组中的最大值，这样可以少判断一个边界条件；

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

const int Inf = 500 * 50000, N = 510;
int weights[N];

int main()
{
    int n, d, max = 0;
    cin >> n >> d;
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
        if (weights[i] > max) max = weights[i];     //recording the max as left;
    }
    int left = max, right = Inf;
    while (left < right) {
        int middle = (left + right) / 2, day = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum + weights[i] > middle) {
                day++;
                sum = 0;
            }
            sum += weights[i];
        }
        day += 1;   // the last day;
        if (day <= d) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    cout << left << endl;
    return 0;
}

Leetcode 函数代码

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int max = 0;
        for (int i = 0; i < weights.size(); i++) {
            if (weights[i] > max) max = weights[i];
        }
        int Inf = 500 * 50000, left = max, right = Inf;
        while (left < right) {
            int middle = (left + right) / 2, day = 0, sum = 0;
            for (int i = 0; i < weights.size(); i++) {
                if (sum + weights[i] > middle) {
                    day++;
                    sum = 0;
                }
                sum += weights[i];
            }
            day += 1;   // the last day;
            if (day <= D) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return left;
    }
};

优化

原来有直接找最大值和求和函数

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;
            // day 为需要运送的天数
            // sum 为当前这一天已经运送的包裹重量之和
            int day = 0, sum = 0;
            for (int i = 0; i < weights.size(); i++) {
                if (sum + weights[i] > mid) {
                    day++;
                    sum = 0;
                }
                sum += weights[i];
            }
            if (day <= D) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};