HardRating 2337

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

stringgreedybinary-indexed-treesegment-tree

解題說明

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

題目描述：給定一個由數字組成的字串 num 和一個整數 k。每次操作可以交換相鄰的兩個數字，最多進行 k 次操作。求能得到的最小整數（以字串形式回傳）。

解題思路：貪心策略：從最高位開始，每次在剩餘 k 步可達的範圍內尋找最小的數字，將其通過相鄰交換移到當前位置。使用 Binary Indexed Tree (BIT) 來高效計算實際需要的交換次數（因為之前的移動會影響後續元素的位置）。

C++ 解法

複雜度分析

時間複雜度：O(n × 10 × log n) = O(n log n) — 每個位置最多嘗試 10 個數字，每次 BIT 操作 O(log n)

空間複雜度：O(n) — BIT 和位置佇列

虛擬碼

1. For each digit 0-9, collect original positions into queues
2. Initialize BIT to track how many elements have been removed before each position
3. For each position in result (left to right):
   a. Try digits 0 to 9 (smallest first)
   b. For digit d, get its earliest remaining position origPos
   c. Actual swap cost = origPos - BIT.query(origPos) (adjusted for previously moved elements)
   d. If cost <= k: use this digit, subtract cost from k, mark as used, update BIT
4. Return result string

其他解法

方法二：暴力模擬 每次在前 k+1 個位置中找最小數字，然後通過相鄰交換移到最前面。不使用 BIT，直接模擬交換。時間複雜度 O(n × k)，可能超時。

方法三：線段樹 用線段樹代替 BIT，維護每個位置是否已被移走。可以支援更複雜的查詢操作。時間複雜度同為 O(n log n)，但常數較大。

延伸思考

如果要求得到的是最大整數而非最小整數，貪心策略需要如何修改？
如果允許非相鄰交換（任意兩個位置可交換），最少需要多少次操作？
為什麼用 BIT 可以正確計算交換次數？移走元素後位置偏移的原理是什麼？

Minimum Possible Integer After at Most K Adjacent Swaps On Digits — CaffeCode