【2022-12-05每日一题】1687. 从仓库到码头运输箱子[Hard]
2022-12-05
3分钟阅读时长
2022-12-05每日一题：1687. 从仓库到码头运输箱子
难度：Hard
标签：线段树 、 队列 、 数组 、 动态规划 、 单调队列 、 堆（优先队列）
你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 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 趟行程。 - 卡车运输第五个箱子，到达码头 3 ，回到仓库，总共 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
方法一：动态规划 + 单调队列
ylb
func boxDelivering(boxes [][]int, portsCount int, maxBoxes int, maxWeight int) int {
n := len(boxes)
ws := make([]int, n+1) // 重量前缀和
cs := make([]int, n) // 行程
for i, box := range boxes {
p, w := box[0], box[1] // [码头， 重量]
ws[i+1] = ws[i] + w
if i < n-1 { // i 不是最后一箱
t := 0
if p != boxes[i+1][0] { // 码头不同
t++
}
cs[i+1] = cs[i] + t
}
}
f, q := make([]int, n+1), []int{0}
for i := 1; i <= n; i++ {
// q 不为空且箱子个数或者重量超过限制，缩短开始位置让i满足限制
for len(q) > 0 && (i-q[0] > maxBoxes || ws[i]-ws[q[0]] > maxWeight) {
q = q[1:]
}
if len(q) > 0 {
f[i] = f[q[0]] + cs[i-1] - cs[q[0]] + 2
}
if i < n {
for len(q) > 0 && f[q[len(q)-1]]-cs[q[len(q)-1]] >= f[i]-cs[i] {
q = q[:len(q)-1]
}
q = append(q, i)
}
}
return f[n]
}
官方
func boxDelivering(boxes [][]int, portsCount int, maxBoxes int, maxWeight int) int {
n := len(boxes)
p, w := make([]int, n+1), make([]int, n+1)
neg, W := make([]int, n+1), 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, g := make([]int, n+1), 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]
}
复杂度分析
时间复杂度：O(n)，其中 n 是数组 boxes 的长度。
空间复杂度：O(n)，即为动态规划的数组 f 和 g，单调队列以及前缀和数组需要使用的空间。