Leetcode P5612 从仓库到码头运输箱子
你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中
b
o
x
e
s
i
=
[
p
o
r
t
s
i
,
w
e
i
g
h
t
i
]
boxes_i = [ports_i, weight_i]
boxesi=[portsi,weighti]。
- 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
示例 3:
输入：boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
输出：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
提示：
-
1
<
=
b
o
x
e
s
.
l
e
n
g
t
h
<
=
1
0
5
1 <= boxes.length <= 10^5
1<=boxes.length<=105
-
1
<
=
p
o
r
t
s
C
o
u
n
t
,
m
a
x
B
o
x
e
s
,
m
a
x
W
e
i
g
h
t
<
=
1
0
5
1 <= portsCount, maxBoxes, maxWeight <= 10^5
1<=portsCount,maxBoxes,maxWeight<=105
-
1
<
=
p
o
r
t
s
i
<
=
p
o
r
t
s
C
o
u
n
t
1 <= ports_i <= portsCount
1<=portsi<=portsCount
-
1
<
=
w
e
i
g
h
t
s
i
<
=
m
a
x
W
e
i
g
h
t
1 <= weights_i <= maxWeight
1<=weightsi<=maxWeight
这是41场双周赛最后一题。题目的大意，有这么多盒子，每一个用(所在港口，重量)表示。我们需要对这么多箱子按顺序运输。每次运输的箱子数量和重量都有一个最大值的限制。在同一个港口的箱子可以直接一起去，不同港口的箱子，需要一次形成从一个港口前往另一个。问一共最少需要几次行程？(开始去港口，从港口回来也各需要1次)
数据量是十万级，所以平方肯定是过不了的。比赛的时候只想到了从i往前递推，找到所有符合条件的以boxes[i]为最后一个元素的一次运输的起点，然后再加上一些优化。。最后就差最后一个样例硬是过不了，有点可惜。。但这也说明
O
(
n
2
)
O(n^2)
O(n2)肯定是行不通的，要思考有没有可以本质优化的地方。
老样子，先写出dp方程：
d
p
[
i
]
=
m
i
n
v
a
l
i
d
j
{
d
p
[
j
−
1
]
+
d
i
f
f
[
j
.
.
.
i
]
+
2
}
dp[i] = min_{valid\ j} \{dp[j - 1] + diff[j...i] + 2\}
dp[i]=minvalid j{dp[j−1]+diff[j...i]+2}
diff[j…i]表示从j到i要跑的港口数。其中j需要满足一定的条件，j到i的boxes数量和重量总和不能超过限制。先不谈j，我们发现光是算diff就可以通过前缀和的形式优化：
d
p
[
i
]
=
m
i
n
v
a
l
i
d
j
{
d
p
[
j
−
1
]
+
s
P
o
r
t
[
i
]
−
s
P
o
r
t
[
j
]
+
2
}
dp[i] = min_{valid\ j}\{dp[j - 1] + sPort[i] - sPort[j] + 2\}
dp[i]=minvalid j{dp[j−1]+sPort[i]−sPort[j]+2}
其中sPort[i]表示从第一个盒子到第i个，累计中间要跑的港口数。可以发现sPort[i] + 2是定值，接下来我们只需要维护这个有效范围内的j的dp[j - 1] - sPort[j]。
不难发现一个i对应的有效的j的范围，可以通过双指针的方法算出来。用pre[i]来表示如果第i个盒子作为最后一个元素，一次运输可以包括到的最前面的元素。于是现在方程变成了这样：
d
p
[
i
]
=
m
i
n
j
≥
p
r
e
[
i
]
{
d
p
[
j
−
1
]
−
s
P
o
r
t
[
j
]
}
+
s
P
o
r
t
[
i
]
+
2
dp[i] = min_{j \geq pre[i]}\{dp[j - 1] - sPort[j]\} +sPort[i]+ 2
dp[i]=minj≥pre[i]{dp[j−1]−sPort[j]}+sPort[i]+2
最后一个问题就是维护
j
≥
p
r
e
[
i
]
j \geq pre[i]
j≥pre[i]这段区间里，
d
p
[
j
−
1
]
−
s
P
o
r
t
[
j
]
dp[j-1]-sPort[j]
dp[j−1]−sPort[j]的最小值。这不就类似于滑动窗口最小值问题吗？可以用单调队列实现。至此，我们设计出了
O
(
n
)
O(n)
O(n)的算法，肯定可以过了。代码如下：
- 第一部分，预处理sPort前缀和数组
- 第二部分，双指针计算pre[i]
- 第三部分，前两部分的预处理完成，用deque维护一个单调队列，计算dp[i]
- 由于和可能达到
1
0
10
10^{10}
1010，所以用了long，要小心
class Solution {
public:
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.size();
long sPort[n + 1], pre[n + 1];
sPort[1] = 0;
for(int i = 2; i <= n; i++) {
sPort[i] = sPort[i - 1];
if (boxes[i - 1][0] != boxes[i - 2][0]) sPort[i]++;
}
pre[1] = 1;
long l = 1, nowBoxes = 1, nowW = boxes[0][1];
for(int i = 2; i <= n; i++) {
nowBoxes++;
nowW += boxes[i - 1][1];
while(nowBoxes > maxBoxes || nowW > maxWeight) {
nowBoxes--;
nowW -= boxes[l - 1][1];
l++;
}
pre[i] = l;
}
deque<pair<long, long>> q;
int res = INT_MAX;
int dp[n + 1];
dp[0] = 0;
for(int i = 1; i <= n; i++) {
while (!q.empty() && q.front().first < pre[i]) q.pop_front();
while (!q.empty() && q.back().second >= dp[i - 1] - sPort[i]) q.pop_back();
q.push_back({i, dp[i - 1] - sPort[i]});
dp[i] = q.front().second + sPort[i] + 2;
}
return dp[n];
}
};
