算法1

(二分) $O(nlog(w))$

C++ 代码

class Solution {
public:
    int shipWithinDays(vector<int>& v, int D) {
        auto p = calBound(v);
        int l = p.first, r = p.second, n = v.size();
        while(l < r) {
            int x = l + (r - l) / 2;
            int t = 0, day = 1;
            for(auto val : v) {
                if(t + val > x) ++day, t = 0;
                t += val;
            }
            if(day <= D) r = x;
            else l = x + 1;
        }
        return r;
    }

    pair<int, int> calBound(vector<int> &v) {
        int sum = 0, x = 0;
        for(auto& t : v) sum += t, x = max(x, t);
        return {x, sum};
    }
};

// 最直观的想法是，枚举可能的值进行划分
// 比如，首先用单日最大重量尝试划分
// 如果不行的话，怎么选择下一个重量呢？
// 根据题意，求最低重量，那么我们可以选择上一步的最小划分，向左或者向右拓展一个
// 但是，如果这样能行，那么直接让第一个划分向右拓展，是等价的
// 这样的时间复杂度是多少呢？
// 最坏情况下，第一个包裹不断向右拓展o(n)次，每次拓展都要进行o(n)复杂度的划分，
// o(n*log(n)) = 5e4*16 = 8e6
// 那我们用2分的方式，不断枚举第一个包裹的长度
// 如果小于D天，就把长度变小，即把日载重量变小; 否则，把长度变大

// !!!这是有问题的，因为最小重量可能处于当前第一个包裹重量和向右拓展一个之间，所以应该枚举的是重量!!!
// 为了知道当前划分是否可行，需要遍历o(n)的时间
// 枚举包裹重量o(log(w)) * 划分o(n)
// w = 500 * 5e4 = 2.5e7 <= 2**25
// 复杂度为o(log(w) * n) <= 25 * 5e4 = 1.25e6