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)，但常數較大且實作複雜。

延伸思考

若箱子可以不按原始順序裝載（可重新排列），最少行程數如何變化？
若有多個倉庫在不同位置，如何修改模型？
若每趟有固定的基礎油費加上距離費用，如何最小化總費用？

Delivering Boxes from Storage to Ports — CaffeCode