import java.util.ArrayDeque;
import java.util.Deque;
// 1687. Delivering Boxes from Storage to Ports
class Solution {
public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
int[] ports = new int[n + 1];
int[] weight = new int[n + 1];
int[] neg = new int[n + 1];
long[] weightPrefixSums = new long[n + 1];
for (int i = 1; i <= n; ++i) {
ports[i] = boxes[i - 1][0];
weight[i] = boxes[i - 1][1];
if (i > 1) {
if (ports[i - 1] != ports[i]) {
neg[i] = neg[i - 1] + 1;
} else {
neg[i] = neg[i - 1];
}
}
weightPrefixSums[i] = weightPrefixSums[i - 1] + weight[i];
}
Deque<Integer> opt = new ArrayDeque<>();
opt.offerLast(0);
int[] minTrips = new int[n + 1];
int[] increment = new int[n + 1];
for (int i = 1; i <= n; ++i) {
while (i - opt.peekFirst() > maxBoxes || weightPrefixSums[i] - weightPrefixSums[opt.peekFirst()] > maxWeight) {
opt.pollFirst();
}
minTrips[i] = increment[opt.peekFirst()] + neg[i] + 2;
if (i != n) {
increment[i] = minTrips[i] - neg[i + 1];
while (!opt.isEmpty() && increment[i] <= increment[opt.peekLast()]) {
opt.pollLast();
}
opt.offerLast(i);
}
}
return minTrips[n];
}
}
学习笔记:
这是一道超级无敌困难的题目。
用到了单调栈,动态规划的点。我一开始怎么都想不出,看了官方题解和好几个题解自后终于慢慢从官方题解演算出过程来。真的太难了,没想到在我生日出这样的题目来刁难我。