你有一辆货运卡车,你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 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 ,然后才能处理第三个箱子)。
1. 状态定义 f[i] : 将前i个箱子搬运到各自码头的最少行程
2. 状态转移 f[i] = f[j] + cost[j + 1] -> f[i] = f[j] + s[i] - s[j + 1];
cost[j + 1] : 搬运j + 1 ~ i的箱子的最少行程
j + 1 体现在 59 和 60 行
3. cost[j + 1, i]的含义是:将j + 1 ~ i 的箱子分别搬运到各自的码头的行程个数
j的取值范围为 i - maxboxes <= j <= i - 1;
若暴力枚举 所有可能的j 时间复杂度为O(n ^ 2);
单调队列优化后的就变成了滑动窗口内寻求最小值 时间复杂度优化后为O(n);
其中cost 可以用前缀和提前预处理 如下代码的s数组
4. 约束条件为 maxBoxes 和 maxWeight
5. w数组重量的前缀和
// 状态转移 f[i] = f[j] + cost[j + 1] -> f[i] = f[j] + s[i] - s[j + 1];
class Solution {
public:
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.size();
vector<long long> f(n + 1, 1e8), s(n + 1, 0), w(n + 1, 0);
s[1] = 1;
f[0] = 0;
for(int i = 1; i <= n; i ++){
int a = boxes[i - 1][0], b = boxes[i - 1][1];
w[i] = w[i - 1] + b;
if(i >= 2)
s[i] = s[i - 1] + (a != boxes[i - 2][0]);
}
deque<int> q;
q.push_back(0);
for(int i = 1; i <= n; i ++){
while(q.size() && i - maxBoxes > q.front() || w[i] - w[q.front()] > maxWeight) q.pop_front();
# f[i] = min(f[i], f[q.front()] + s[i] - s[q.front() + 1] + 2);
# while(q.size() && f[q.back()] - s[q.back() + 1] >= f[i] - s[i]) q.pop_back();
q.push_back(i);
}
return f[n];
}
};