【10.6】队列-解从仓库到码头运输箱子
一、题目
你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [portsi, weighti] 。
portsi表示第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 。
提示：
二、解题思路
这个问题可以通过动态规划（Dynamic Programming, DP）结合单调队列优化来解决。我们需要计算将箱子从仓库运送到码头所需的最少行程次数。
思路：
1. **状态定义**：
- 设 `dp[i]` 表示运输前 `i` 个箱子所需的最少行程次数。
2. **状态转移**：
- 对于每个箱子 `i`，我们需要找到一个 `j`（`j < i`），使得从 `j+1` 到 `i` 的箱子可以在一趟运输中完成。
- 转移方程为：
dp[i]=min(dp[j]+cost(j+1,i))
其中 `cost(j+1, i)` 表示从 `j+1` 到 `i` 的箱子运输所需的行程次数。
3. **行程次数计算**：
- 对于一趟运输，行程次数包括：
- 从仓库出发，依次到达每个箱子的目的地码头。
- 最后返回仓库。
- 如果相邻两个箱子的目的地码头相同，则不需要额外的行程。
4. **单调队列优化**：
- 使用单调队列维护满足 `maxBoxes` 和 `maxWeight` 限制的区间 `[j+1, i]`。
- 通过滑动窗口的方式，快速找到最优的 `j`。
三、代码实现
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits> // 用于 INT_MAX
using namespace std;
// 功能：计算配送所有箱子所需的最小行程次数
// 参数：
// boxes - 一个二维向量，其中 boxes[i] = [port_i, weight_i] 表示第 i 个箱子的港口编号和重量
// portsCount - 港口的总数
// maxBoxes - 卡车最多可以装载的箱子数量
// maxWeight - 卡车最多可以装载的总重量
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.size(); // 箱子的总数
vector<int> dp(n + 1, INT_MAX); // dp[i] 表示配送前 i 个箱子的最小行程次数
dp[0] = 0; // 0 个箱子需要 0 次行程，初始状态
// 单调队列，用于优化动态规划
deque<int> dq;
dq.push_back(0); // 初始时队列中只有第 0 个元素
int totalWeight = 0; // 当前区间内箱子的总重量
int totalTrips = 0; // 当前区间内的行程次数（在不同港口之间转移会增加行程次数）
// 遍历所有箱子
for (int i = 1; i <= n; ++i) {
// 累加当前箱子的重量
totalWeight += boxes[i - 1][1];
// 如果当前箱子与前一个箱子的港口不同，则行程次数增加
if (i > 1 && boxes[i - 1][0] != boxes[i - 2][0]) {
totalTrips++;
}
// 如果队列不为空且当前区间不满足条件（箱子数量或总重量超出限制），则从队列前端移除元素
while (!dq.empty() && (i - dq.front() > maxBoxes || totalWeight > maxWeight)) {
int j = dq.front();
dq.pop_front();
totalWeight -= boxes[j][1]; // 更新区间内的总重量
// 如果移除的箱子与下一个箱子港口不同，行程次数减少
if (j + 1 < i && boxes[j][0] != boxes[j + 1][0]) {
totalTrips--;
}
}
// 如果队列不为空，则更新 dp[i] 的值
if (!dq.empty()) {
int j = dq.front();
dp[i] = dp[j] + totalTrips + 2; // 加 2 是因为每次配送都需要从仓库出发并最终返回仓库
}
// 维护单调队列，确保队列中 dp 值是单调递增的
while (!dq.empty() && dp[dq.back()] >= dp[i]) {
dq.pop_back();
}
dq.push_back(i); // 当前索引入队
}
// 返回配送所有箱子的最小行程次数
return dp[n];
}
int main() {
// 示例代码，用于测试 boxDelivering 函数
// 示例 1
vector<vector<int>> boxes1 = {
{1, 1}, {2, 1}, {1, 1}};
int portsCount1 = 2, maxBoxes1 = 3, maxWeight1 = 3;
cout << "结果: " << boxDelivering(boxes1, portsCount1, maxBoxes1, maxWeight1) << endl;
return 0;
}
时间复杂度：O(n)O(n)，其中 nn 是箱子的数量。
空间复杂度：O(n)O(n)，用于存储动态规划数组和单调队列。