HardRating 2610
1687. Delivering Boxes from Storage to Ports
arraydynamic-programmingsegment-treequeueheap-priority-queueprefix-summonotonic-queue
解題說明
Delivering Boxes from Storage to Ports
題目描述:有 n 個箱子要從倉庫運送到不同港口,每次運送最多搬 maxBoxes 個箱子、總重量不超過 maxWeight。每趟從倉庫出發按順序送達,最後回到倉庫。相鄰箱子若目的港口相同不額外計行程。求最少的總行程數。
解題思路:使用動態規劃配合單調佇列優化。定義 dp[i] 為送完前 i 個箱子的最少行程數。轉移為 dp[i] = min_{valid j}(dp[j] - preDiff[j]) + preDiff[i] + 2,其中 preDiff 為相鄰港口不同的前綴和。利用單調佇列維護 dp[j] - preDiff[j] 的最小值,同時移除超過箱子數或重量限制的候選 j,實現 O(n) 時間。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個元素最多進出單調佇列各一次,前綴和計算也是線性。
空間複雜度:O(n) — 前綴和陣列、DP 陣列和單調佇列各需 O(n) 空間。
虛擬碼
1. Compute diff[i] = 1 if boxes[i].port != boxes[i-1].port, else 0
2. Compute prefix sums: preDiff (port changes), preW (weights)
3. Define val(j) = dp[j] - preDiff[j]
4. Init dp[0] = 0, monotonic deque with {0}
5. For i = 1 to n:
a. Remove front of deque while box count (i - front) > maxBoxes or weight exceeds maxWeight
b. dp[i] = val(deque.front) + preDiff[i] + 2
c. Remove back of deque while val(i) <= val(deque.back)
d. Push i to deque
6. Return dp[n]其他解法
樸素 DP O(n^2):對每個 i 枚舉所有合法的起點 j,直接計算 dp[i] = min(dp[j] + cost(j+1,i) + 2)。容易理解但在 n 較大時超時。
線段樹優化 DP:用線段樹維護區間最小值代替單調佇列,支持更靈活的查詢。時間 O(n log n),空間 O(n),但常數較大且實作複雜。
延伸思考
- 若箱子可以不按原始順序裝載(可重新排列),最少行程數如何變化?
- 若有多個倉庫在不同位置,如何修改模型?
- 若每趟有固定的基礎油費加上距離費用,如何最小化總費用?