你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 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 。
提示：
1 <= boxes.length <= 1051 <= portsCount, maxBoxes, maxWeight <= 1051 <= portsi <= portsCount1 <= weightsi <= maxWeight
方法一：动态规划 + 单调队列优化
前言
为了叙述方便，我们记箱子的数量为 n，它们的目的地分别为 p_1, \cdots, p_n，重量分别为 w_1, \cdots, w_n。
记 W_i 表示 w 的前缀和，即：
W_i = \left{
\begin{aligned}
& 0, && i = 0 \
& \sum_{k=1}^i w_i, && i > 0
\end{aligned} \right.
这样我们可以用 W_i - W_{j-1 方便地表示第 i 个到第 j 个箱子的重量，并与 maxWeight 进行比较。
记示性函数 \mathbb{I}(i) 表示 p_i 和 p_{i+1 是否不等，即：
\mathbb{I}(i) = \begin{cases}
0, \quad p_i = p_{i+1} \
1, \quad p_i \neq p_{i+1}
\end{cases}
记 neg}(i, j) 表示 p_i, \cdots, p_j 相邻两项不等的次数，即：
\textit{neg}(i, j) = \sum_{k=i}^{j-1} \mathbb{I}(k)
这样我们可以用 neg}(i, j) + 2 方便地求出一次性运送第 i 个到第 j 个箱子需要的行程次数，这里的 +2 表示来回需要的 2 次。
为了便于快速计算 neg}(i, j)，我们也可以使用前缀和的方式进行存储。记 neg}_i = \textit{neg}(1, i) 表示前缀和，那么 neg}(i, j) = \textit{neg}j - \textit{neg}{i 可以在 O(1) 的时间求出。
注意：这里是 neg}j - \textit{neg}{i 而不是 neg}j - \textit{neg}{i-1，读者可以思考一下其原因。
思路与算法
我们可以使用动态规划解决本题。
记 f_i 表示运送前 i 个箱子需要的最少行程次数，这里的「前 i 个箱子」指的是目的地为 p_1, \cdots, p_i 的 i 个箱子。我们可以写出状态转移方程：
\begin{aligned}
& f_i = \min \big{ f_j + \textit{neg}(j+1,i) + 2 \big} \\
\text{subject to} \quad &
\begin{cases} 0 \leq j < i \
i-j \leq \textit{maxBoxes} \
W_i-W_j \leq \textit{maxWeight}
\end{cases}
\end{aligned}
即枚举上一次运送的最后一个箱子为 j（这里的 j 可以为 0，表示这一次是第一次运送箱子），那么这一次运送的箱子为 [j+1, i]。箱子的数量不超过 maxBoxes，重量之和不能超过 maxWeight。运送的行程次数即为 p_{j+1}, \cdots, p_i 相邻两项不等的次数 neg}(j+1, i) 加上来回的 2 次。
边界条件为 f_0 = 0，最终答案即为 f_n。
优化
然而上述动态规划的时间复杂度为 O(n^2)，我们需要进行优化。我们将 neg}(j+1, i) 拆分成两个前缀和的差，即：
\textit{neg}(j+1, i) = \textit{neg}i - \textit{neg}{j+1}
带入原状态转移方程：
\begin{aligned}
f_i &= \min \big{ f_j + \textit{neg}(j+1,i) + 2 \big} \
&= \min \big{ f_j + \textit{neg}i - \textit{neg}{j+1} + 2 \big} \
&= \min \big{ f_j - \textit{neg}_{j+1} \big} + \textit{neg}_i + 2
\end{aligned}
由于 neg}_i 和 2 都是与 j 无关的项，因此可以从 \min{ \cdot \ 中提取出来。
记 g_j = f_j - \textit{neg}_{j+1，状态转移方程即为：
f_i = \min { g_j } + \textit{neg}(i) + 2
如果只有 0 \leq j < i 的限制条件，那么我们实时维护 g_j 的最小值进行 O(1) 的转移即可。但现在有 i-j \leq \textit{maxBoxes 和 W_i-W_j \leq \textit{maxWeight 这两个额外的限制条件，最小的 g_j 对应的 j 不一定满足限制。
我们可以将两个额外的限制看成：
\begin{cases}
j \geq i - \textit{maxBoxes} \
W_j \geq W_i - \textit{maxWeight}
\end{cases}
注意到两个不等式右侧的值都是随着 i 的递增而递增的，因此如果当 i=i_0 时，某个 j_0 不满足不等式限制，那么当 i>i_0 时，j_0 将永远不可能重新满足条件。
因此我们就可以使用单调队列对动态规划进行优化，对于两个可以进行转移的 g_{j_0 和 g_{j_1，在 j_0 < j_1 的前提下：
如果 g_{j_0} < g_{j_1，那么我们需要将 g_{j_0 和 g_{j_1 都保留下来，这是因为当 j_0 还满足限制时，g_{j_0 比 g_{j_1 更优；而当 j_0 不满足限制后，g_{j_1 可能会代替 g_{j_0，成为新的最优转移；
如果 g_{j_0} \geq g_{j_1，那么我们只需要将 g_{j_1 保留下来即可。这是因为当 j_0 还满足限制时，选择 g_{j_1 并不会更差，并且 j_1 可以满足限制的时间（即随着 i 的递增）更久。
因此，我们使用一个队列存储所有需要被保留的 g_j（存储下标 j 即可），从队首到队尾，j 的值单调递增，g_j 的值也单调递增。在进行状态转移求解 f_i 时：
状态转移需要的时间为 O(1)。而对于单调队列的部分，每一个 g_i 会被加入队列恰好一次，并且被从队列中弹出最多一次，因此均摊时间为 O(1)。这样一来，动态规划的时间复杂度降低为 O(n)。
代码
代码中很多变量都是为了和文字部分保持一致而添加的，如果熟练了掌握了本题使用的方法，可以优化掉一些变量。
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.size();
vector<int> p(n + 1), w(n + 1), neg(n + 1);
vector<long long> W(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]);
}
W[i] = W[i - 1] + w[i];
}
deque<int> opt = {0};
vector<int> f(n + 1), g(n + 1);
for (int i = 1; i <= n; ++i) {
while (i - opt.front() > maxBoxes || W[i] - W[opt.front()] > maxWeight) {
opt.pop_front();
}
f[i] = g[opt.front()] + neg[i] + 2;
if (i != n) {
g[i] = f[i] - neg[i + 1];
while (!opt.empty() && g[i] <= g[opt.back()]) {
opt.pop_back();
}
opt.push_back(i);
}
}
return f[n];
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| 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];
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution:
def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
def getArray() -> List[int]:
return [0] * (n + 1)
n = len(boxes)
p, w, neg, W = getArray(), getArray(), getArray(), getArray()
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, g = getArray(), getArray()
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]
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| typedef struct {
int *elements;
int rear, front;
int capacity;
} MyCircularDeque;
MyCircularDeque* myCircularDequeCreate(int k) {
MyCircularDeque *obj = (MyCircularDeque *)malloc(sizeof(MyCircularDeque));
obj->capacity = k + 1;
obj->rear = obj->front = 0;
obj->elements = (int *)malloc(sizeof(int) * obj->capacity);
return obj;
}
bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
if ((obj->rear + 1) % obj->capacity == obj->front) {
return false;
}
obj->front = (obj->front - 1 + obj->capacity) % obj->capacity;
obj->elements[obj->front] = value;
return true;
}
bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
if ((obj->rear + 1) % obj->capacity == obj->front) {
return false;
}
obj->elements[obj->rear] = value;
obj->rear = (obj->rear + 1) % obj->capacity;
return true;
}
bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
if (obj->rear == obj->front) {
return false;
}
obj->front = (obj->front + 1) % obj->capacity;
return true;
}
bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
if (obj->rear == obj->front) {
return false;
}
obj->rear = (obj->rear - 1 + obj->capacity) % obj->capacity;
return true;
}
int myCircularDequeGetFront(MyCircularDeque* obj) {
if (obj->rear == obj->front) {
return -1;
}
return obj->elements[obj->front];
}
int myCircularDequeGetRear(MyCircularDeque* obj) {
if (obj->rear == obj->front) {
return -1;
}
return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity];
}
bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
return obj->rear == obj->front;
}
bool myCircularDequeIsFull(MyCircularDeque* obj) {
return (obj->rear + 1) % obj->capacity == obj->front;
}
void myCircularDequeFree(MyCircularDeque* obj) {
free(obj->elements);
free(obj);
}
int boxDelivering(int** boxes, int boxesSize, int* boxesColSize, int portsCount, int maxBoxes, int maxWeight) {
int n = boxesSize;
int p[n + 1], w[n + 1], neg[n + 1];
long long W[n + 1];
memset(neg, 0, sizeof(neg));
memset(W, 0, sizeof(W));
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]);
}
W[i] = W[i - 1] + w[i];
}
int f[n + 1], g[n + 1];
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
MyCircularDeque *opt = myCircularDequeCreate(n + 1);
myCircularDequeInsertLast(opt, 0);
for (int i = 1; i <= n; ++i) {
while (i - myCircularDequeGetFront(opt) > maxBoxes ||
W[i] - W[myCircularDequeGetFront(opt)] > maxWeight) {
myCircularDequeDeleteFront(opt);
}
f[i] = g[myCircularDequeGetFront(opt)] + neg[i] + 2;
if (i != n) {
g[i] = f[i] - neg[i + 1];
while (!myCircularDequeIsEmpty(opt) && g[i] <= g[myCircularDequeGetRear(opt)]) {
myCircularDequeDeleteLast(opt);
}
myCircularDequeInsertLast(opt, i);
}
}
myCircularDequeFree(opt);
return f[n];
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| 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];
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| 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]
}
|
复杂度分析
