分析

• 本题的考点：二分。

• 因为D最小是1，因此本题一定存在答案，因为我们可以一次把所有物品运完。

• 本题采用二分，二分的左端点l应该取数组元素的最大值，否则的话这个物品无法运输过去，右端点r取数组元素之和。

• 对于每次考察的运输量mid，设days(mid)返回在运输量为mid的情况下需要的运输天数，如果$days(mid) \le D$，则说明mid是一个合法解，右端点更新为mid，否则左端点更新为mid+1。

代码

• C++

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {

        int l = 0, r = 0;
        for (auto w : weights) l = max(l, w), r += w;

        while (l < r) {
            int mid = l + r >> 1;
            if (days(weights, mid) <= D) r = mid;
            else l = mid + 1;
        }
        return r;
    }

    // k -> days(k) : 是一个减函数。如果船舶最低载重为k, 需要运输的天数
    int days(vector<int> &w, int k) {

        int res = 0;
        int i = 0, t = k;
        while (i < w.size()) {
            while (i < w.size() && t >= w[i]) t -= w[i++];
            res++;
            t = k;
        }
        return res;
    }
};

• Java

class Solution {
    public int shipWithinDays(int[] weights, int D) {

        int l = 0, r = 0;
        for (int w : weights) {
            l = Math.max(l, w);
            r += w;
        }
        while (l < r) {
            int mid = l + r >> 1;
            if (days(weights, mid) <= D) r = mid;
            else l = mid + 1;
        }
        return r;
    }

    // k -> days(k) : 是一个减函数。如果船舶最低载重为k, 需要运输的天数
    private int days(int[] w, int k) {

        int res = 0;
        int i = 0, t = k;
        while (i < w.length) {
            while (i < w.length && t >= w[i]) t -= w[i++];
            res++;
            t = k;
        }
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times log(m))$，n为物品个数，m为物品重量之和。

• 空间复杂度：$O(1)$。