這是一道經典的算法競賽題目,源自 JLOI 2013。問題描述了兩堆物品(M=2),每個物品有唯一的優先級(數值越大優先級越高)。操作規則是:只能移動堆頂物品,可將其移至另一堆頂端;若該物品是當前所有物品中優先級最高者,可直接刪除(不計步數)。目標是求刪除所有物品所需的最小移動步數。
由於優先級互不相同且 M=2,問題可轉化為:給定兩個棧(頂在前),每次操作可將棧頂元素移至另一棧頂端,或若其為全局最大則彈出。最終需清空兩棧。這本質上是一個排序與逆序對計數問題。
關鍵洞見:物品最終刪除順序必然是優先級從高到低。考慮優先級為 k 的物品,它被刪除時,所有優先級 > k 的物品已被移除。因此,我們可以按優先級從大到小處理,維護當前兩堆的「有效前綴」。
將所有物品按輸入順序編號 1 到 N(N = N1 + N2),第一堆佔 1..N1,第二堆佔 N1+1..N。對優先級離散化映射為 1..N(值越大優先級越高)。
定義 f[i] 為優先級第 i 高的物品在原始序列中的位置。我們按優先級從高到低(i = N 到 1)模擬刪除過程。此時需要知道該物品在「當前剩餘序列」中的相對位置,以計算移動步數。
引入樹狀數組(Fenwick Tree)維護已刪除物品的位置。query(x) 返回位置 x 前(含 x)未被刪除的物品數。具體實現中,query(x) = x - sum(x),其中 sum(x) 為前綴已刪除數。
維護變量 tmp 表示第一堆當前剩餘物品數(即分界點)。對於優先級第 i 高的物品,其當前位置 pos = query(f[i])。若 pos > tmp,說明它在第二堆,需移動 pos - (tmp + 1) 步到第一堆頂端再刪除;反之在第一堆,需移動 tmp - pos 步。刪除後更新 tmp = pos - 1,並將 f[i] 標記為已刪除(change(f[i]))。
此貪心策略最優,因為高優先級物品必須優先清除,且移動路徑唯一。樹狀數組支持 O(log N) 單點更新與前綴查詢,總複雜度 O(N log N),滿足 N ≤ 100,000 限制。
提供的 C++ 代碼採用離散化 + 樹狀數組,讀入優化、逆序處理、位置查詢與更新均符合上述邏輯。注意 map 用於記錄原始位置,排序後重新賦值實現離散化。
本題展示了如何將棧操作問題轉化為順序統計問題,利用樹狀數組高效維護動態序列中的相對位置,是數據結構在算法競賽中經典應用案例。