从仓库到码头运输箱子

1687. 从仓库到码头运输箱子

你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。

给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [ports_i, weight_i] 。

ports_i 表示第 i 个箱子需要送达的码头， weights_i 是第 i 个箱子的重量。
portsCount 是码头的数目。
maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。

箱子需要按照 数组顺序 运输，同时每次运输需要遵循以下步骤：

卡车从 boxes 队列中按顺序取出若干个箱子，但不能违反 maxBoxes 和 maxWeight 限制。
对于在卡车上的箱子，我们需要 按顺序 处理它们，卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头，那么不需要 额外行程 ，箱子也会立马被卸货。
卡车上所有箱子都被卸货后，卡车需要 一趟行程 回到仓库，从箱子队列里再取出一些箱子。

卡车在将所有箱子运输并卸货后，最后必须回到仓库。

请你返回将所有箱子送到相应码头的 最少行程 次数。

示例 1：

输入：boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
输出：4
解释：最优策略如下：
- 卡车将所有箱子装上车，到达码头 1 ，然后去码头 2 ，然后再回到码头 1 ，最后回到仓库，总共需要 4 趟行程。
所以总行程数为 4 。
注意到第一个和第三个箱子不能同时被卸货，因为箱子需要按顺序处理（也就是第二个箱子需要先被送到码头 2 ，然后才能处理第三个箱子）。

示例 2：

输入：boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
输出：6
解释：最优策略如下：
- 卡车首先运输第一个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第二、第三、第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五个箱子，到达码头 3 ，回到仓库，总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。

示例 3：

输入：boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
输出：6
解释：最优策略如下：
- 卡车运输第一和第二个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第三和第四个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五和第六个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。

示例 4：

输入：boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7
输出：14
解释：最优策略如下：
- 卡车运输第一个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第二个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第三和第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第六和第七个箱子，到达码头 3 ，然后去码头 4 ，然后回到仓库，总共 3 趟行程。
- 卡车运输第八和第九个箱子，到达码头 1 ，然后去码头 5 ，然后回到仓库，总共 3 趟行程。
总行程数为 2 + 2 + 2 + 2 + 3 + 3 = 14 。

提示：

1 <= boxes.length <= 10⁵
1 <= portsCount, maxBoxes, maxWeight <= 10⁵
1 <= ports_i <= portsCount
1 <= weights_i <= maxWeight

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) { } };

java 解法, 执行用时: 38 ms, 内存消耗: 84.9 MB, 提交时间: 2022-12-05 09:28:54

/**
 * 状态集合：
    dp[i]:运送前i个箱子需要的最少行程次数
状态计算：
    dp[i] = dp[j - 1] + cost[j, i],  (i - maxB + 1 <= j <= i)
    cost[j, i]代表第k~第i个箱子的行程次数
 */
class Solution {
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.length, dp = 0;
        PriorityQueue<int[]> q = new PriorityQueue<int[]>((a, b)->a[1] - b[1]);
        int dif = 0, wei = 0;
        for (int i = 1; i <= n; i++) {
            int cur = dp + 2;
            dif += i >= 2 && boxes[i - 1][0] != boxes[i - 2][0] ? 1 : 0;//cost[i, i] = 2
            wei += boxes[i - 1][1]; 
            q.add(new int[]{i, cur - dif, boxes[i - 1][1] - wei}); 
            while (q.peek()[0] <= i - maxBoxes || q.peek()[2] + wei > maxWeight) q.poll();
            dp = q.peek()[1] + dif; 
        }  
        return dp;
    } 
}

java 解法, 执行用时: 22 ms, 内存消耗: 90.5 MB, 提交时间: 2022-12-05 09:27:50

/**
 * 状态集合：
    dp[i]:运送前i个箱子需要的最少行程次数
状态计算：
    dp[i] = dp[j - 1] + cost[j, i],  (i - maxB + 1 <= j <= i)
    cost[j, i]代表第k~第i个箱子的行程次数
 */
class Solution {
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.length, dp = 0;
        Deque<int[]> q = new ArrayDeque<int[]>();
        int dif = 0, wei = 0;
        for (int i = 1; i <= n; i++) {
            int cur = dp + 2;
            dif += i >= 2 && boxes[i - 1][0] != boxes[i - 2][0] ? 1 : 0;//cost[i, i] = 2
            wei += boxes[i - 1][1];
            while (!q.isEmpty() && q.peekLast()[1] + dif >= cur) q.pollLast();
            q.add(new int[]{i, cur - dif, boxes[i - 1][1] - wei}); 
            while (q.peekFirst()[0] <= i - maxBoxes || q.peekFirst()[2] + wei > maxWeight) q.pollFirst();
            dp = q.peekFirst()[1] + dif; 
        }  
        return dp;
    } 
}

java 解法, 执行用时: 23 ms, 内存消耗: 77.2 MB, 提交时间: 2022-12-05 09:26:10

/**
 * 状态集合：
    dp[i]:运送前i个箱子需要的最少行程次数
状态计算：
    dp[i] = dp[j - 1] + cost[j, i],  (i - maxB + 1 <= j <= i)
    cost[j, i]代表第k~第i个箱子的行程次数
 */
class Solution {
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.length;
        int[] dp = new int[n + 5];
        Arrays.fill(dp, 0x3f3f3f3f);
        dp[0] = 0;
        Deque<int[]> q = new ArrayDeque<int[]>(); //双端队列
        int dif = 0, wei = 0;
        for (int i = 1; i <= n; i++) {
            int cur = dp[i - 1] + 2;//cur为每次滑动窗口增加的值即dp[i-1]+cost[i,i]
            dif += i >= 2 && boxes[i - 1][0] != boxes[i - 2][0] ? 1 : 0;//dif为运输累加值，由于我们无法直接在队列中进行修改，那么可以考虑增加一个累加值
            wei += boxes[i - 1][1]; //重量要加上当前箱子的重量
            while (!q.isEmpty() && q.peekLast()[1] + dif >= cur) q.pollLast(); //构造一个单调递增的队列
            q.add(new int[]{i, cur - dif, boxes[i - 1][1] - wei}); 
            //判断左端队头是否在窗口外 并且重量不能超过最大重量
            while (q.peekFirst()[0] <= i - maxBoxes || q.peekFirst()[2] + wei > maxWeight) q.pollFirst(); 
            dp[i] = q.peekFirst()[1] + dif; 
        }  
        return dp[n];
    } 
}

python3 解法, 执行用时: 476 ms, 内存消耗: 48.3 MB, 提交时间: 2022-12-05 09:23:52

class Solution:
    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
        def getArray(k: int) -> List[int]:
            return [0] * k
        
        n = len(boxes)
        # p[i] 目的地，w[i] 重量，Wi w的前缀和；neg[i] p[i]相邻两项不等次数
        p, w, neg, W = getArray(n+1), getArray(n+1), getArray(n+1), getArray(n+1)

        for i in range(1, n + 1):
            p[i], w[i] = boxes[i - 1]
            if i > 1:
                neg[i] = neg[i - 1] + (p[i - 1] != p[i])
            W[i] = W[i - 1] + w[i]
        
        opt = deque([0])
        # f[i] 运送前i个箱子最少行程；
        f, g = getArray(n+1), getArray(n+1)
        
        for i in range(1, n + 1):
            while i - opt[0] > maxBoxes or W[i] - W[opt[0]] > maxWeight:
                opt.popleft()
            
            f[i] = g[opt[0]] + neg[i] + 2
            
            if i != n:
                g[i] = f[i] - neg[i + 1]
                while opt and g[i] <= g[opt[-1]]:
                    opt.pop()
                opt.append(i)
        
        return f[n]

java 解法, 执行用时: 28 ms, 内存消耗: 78 MB, 提交时间: 2022-12-05 09:17:27

class Solution {
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.length;
        int[] p = new int[n + 1];
        int[] w = new int[n + 1];
        int[] neg = new int[n + 1];
        long[] W = new long[n + 1];
        for (int i = 1; i <= n; ++i) {
            p[i] = boxes[i - 1][0];
            w[i] = boxes[i - 1][1];
            if (i > 1) {
                neg[i] = neg[i - 1] + (p[i - 1] != p[i] ? 1 : 0);
            }
            W[i] = W[i - 1] + w[i];
        }

        Deque<Integer> opt = new ArrayDeque<Integer>();
        opt.offerLast(0);
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        for (int i = 1; i <= n; ++i) {
            while (i - opt.peekFirst() > maxBoxes || W[i] - W[opt.peekFirst()] > maxWeight) {
                opt.pollFirst();
            }

            f[i] = g[opt.peekFirst()] + neg[i] + 2;

            if (i != n) {
                g[i] = f[i] - neg[i + 1];
                while (!opt.isEmpty() && g[i] <= g[opt.peekLast()]) {
                    opt.pollLast();
                }
                opt.offerLast(i);
            }
        }

        return f[n];
    }
}

golang 解法, 执行用时: 260 ms, 内存消耗: 22 MB, 提交时间: 2022-12-05 09:17:04

func boxDelivering(boxes [][]int, portsCount int, maxBoxes int, maxWeight int) int {
    n := len(boxes)
    p := make([]int, n+1)
    w := make([]int, n+1)
    neg := make([]int, n+1)
    W := make([]int, n+1)
    for i := 1; i <= n; i++ {
        p[i] = boxes[i-1][0]
        w[i] = boxes[i-1][1]
        if i > 1 {
            neg[i] = neg[i-1]
            if p[i-1] != p[i] {
                neg[i]++
            }
        }
        W[i] = W[i-1] + w[i]
    }

    opt := []int{0}
    f := make([]int, n+1)
    g := make([]int, n+1)

    for i := 1; i <= n; i++ {
        for i-opt[0] > maxBoxes || W[i]-W[opt[0]] > maxWeight {
            opt = opt[1:]
        }

        f[i] = g[opt[0]] + neg[i] + 2

        if i != n {
            g[i] = f[i] - neg[i+1]
            for len(opt) > 0 && g[i] <= g[opt[len(opt)-1]] {
                opt = opt[:len(opt)-1]
            }
            opt = append(opt, i)
        }
    }

    return f[n]
}

javascript 解法, 执行用时: 240 ms, 内存消耗: 80.4 MB, 提交时间: 2022-12-05 09:16:48

/**
 * @param {number[][]} boxes
 * @param {number} portsCount
 * @param {number} maxBoxes
 * @param {number} maxWeight
 * @return {number}
 */
var boxDelivering = function(boxes, portsCount, maxBoxes, maxWeight) {
    const n = boxes.length;
    const p = new Array(n + 1).fill(0);
    const w = new Array(n + 1).fill(0);
    const neg = new Array(n + 1).fill(0);
    const W = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        p[i] = boxes[i - 1][0];
        w[i] = boxes[i - 1][1];
        if (i > 1) {
            neg[i] = neg[i - 1] + (p[i - 1] != p[i] ? 1 : 0);
        }
        W[i] = W[i - 1] + w[i];
    }

    const opt = [0];
    const f = new Array(n + 1).fill(0);
    const g = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        while (i - opt[0] > maxBoxes || W[i] - W[opt[0]] > maxWeight) {
            opt.shift();
        }

        f[i] = g[opt[0]] + neg[i] + 2;

        if (i !== n) {
            g[i] = f[i] - neg[i + 1];
            while (opt.length && g[i] <= g[opt[opt.length - 1]]) {
                opt.pop();
            }
            opt.push(i);
        }
    }

    return f[n];
};

上一题

下一题

详情