首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

BZOJ 3192 [JLOI2013] 刪除物品:雙堆優先級刪除問題的最優解法

     編輯:關於C++

問題背景

這是一道經典的算法競賽題目,源自 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 用於記錄原始位置,排序後重新賦值實現離散化。

總結

本題展示了如何將棧操作問題轉化為順序統計問題,利用樹狀數組高效維護動態序列中的相對位置,是數據結構在算法競賽中經典應用案例。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved