解題說明
Dota2 Senate
題目描述:Radiant(R)與 Dire(D)兩派參議員輪流行使權利,每人可以禁止對方一名參議員的後續權利。按字串順序循環,直到某派全部存活參議員宣布勝利。
解題思路:貪心 + 雙佇列:分別用 qR 和 qD 存各派的索引。每輪彈出兩個較早的索引比較:索引小者勝(先行動),將其索引加 n 重新入隊(代表下一輪仍可行動),輸者永久出局。重複直到其中一個佇列為空。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每位參議員最多在佇列中循環有限次,整體線性。
空間複雜度:O(n) — 兩個佇列合計最多存放 n 個索引。
虛擬碼
1. Initialize qR, qD with indices of 'R' and 'D' senators 2. n = len(senate) 3. While qR and qD are both non-empty: a. r = qR.front(), pop; d = qD.front(), pop b. If r < d: qR.push(r + n) // R eliminates D c. Else: qD.push(d + n) // D eliminates R 4. If qR is empty: return "Dire" 5. Else: return "Radiant"
其他解法
模擬 + ban 計數器:用單一佇列遍歷所有參議員,維護 banR 和 banD 計數器。遇到 R 且 banR > 0 則禁掉(banR--),否則 banD++;D 同理。模擬完一輪再看誰還剩。邏輯等價但實作稍複雜。
遞迴模擬:每輪掃描一次字串、消除對立方最早的參議員,重複到只剩一派。時間 O(n²) 效率較差。
延伸思考
- 若每位參議員可以禁止對方「最多 k 名」(而非 1 名),策略如何改變?
- 若雙方均採取最優策略,在什麼初始條件下 Radiant 必勝?
- 如何修改貪心策略以最大化獲勝方剩餘的參議員人數?