从仓库到码头运输箱子

题目

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

---

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

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

• ports​​i 表示第 i 个箱子需要送达的码头， weightsi 是第 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 趟行程。
- 卡车运输第五个箱子，到达码头 2 ，回到仓库，总共 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^5
• 1 <= portsCount, maxBoxes, maxWeight <= 10^5
• 1 <= ports​​i <= portsCount
• 1 <= weightsi <= maxWeight

题解

方法一：

思路

单调队列优化dp

我们用$p_i$表示前i个箱子港口编号相邻不相同的个数。对于单独的第一个数$p_1=0$，在第一个箱子前设置与第一个箱子港口相同的哨兵，$p_{0} = p_{1}$。对于前i个到前j个箱子（i<=j）相邻不同编号的个数是$p_{j}-p_{i}$。通过观察测试用例可以看出这与以往的前缀和不同。

$w_i$为前i个箱子的重量和，$w_0 = 0$。

$P$是车载箱子最大个数。

$W$是车载最大重量。

令f_i为前i个箱子的最小移动次数。初始化f_0 = 0。

容易想到$f_i = \min \limits_{i-P \le j<i, w_i-w_j \le W} \lbrace f_j+p_i-p_{j+1}+2 \rbrace $

现在将式子转化为$f_i = \min \limits_{i-P \le j < i, w_i-w_j \le W} \lbrace f_j-p_{j+1} \rbrace +p_i+2$，对于求$\min \limits_{i-P \le j<i, w_i-w_j \le W} \lbrace f_j-p_{j+1} \rbrace $可以维护单调递减队列，每次O(1)求得状态转移。总时间复杂度O(n)。

代码

class Solution {
public:
    using ll = long long;
    int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.size();
        vector<ll> p(n+1), w(n+1);
        for (int i=2; i<=n; i++) {
            p[i] = p[i-1] + (boxes[i-1][0] != boxes[i-2][0]);
        }
        for (int i=1; i<=n; i++) {
            w[i] = w[i-1] + boxes[i-1][1];
        }
        vector<ll> f(n+1);
        // vector<int> q(n+5);//队列存储箱子编号
        auto cmp = [&](int a, int b) {
            return f[a]-p[a+1] > (f[b]-p[b+1]);
        };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);//小根堆，f[i]-p[i+1]
        // int s = 0, e = 1;
        q.emplace(0);
        for (int i=1; i<=n; i++) {
            // while (q[s]+maxBoxes<i || w[i]-w[q[s]]>maxWeight) s++;
            while (q.top()+maxBoxes<i || w[i]-w[q.top()]>maxWeight) q.pop();
            // f[i] = f[q[s]]+p[i]-p[q[s]+1]+2;
            f[i] = f[q.top()]+p[i]-p[q.top()+1]+2;
            // while (s<e && i<n && f[q[e-1]]-p[q[e-1]+1] > f[i]-p[i+1]) e--;
            // q[e++] = i;
            if (i<n) q.emplace(i);
        }
        // for (int i=1; i<=n; i++) {
        //     cout << f[i] << " ";
        // }
        return f[n];
    }
};