2530. Maximal Score After Applying K Operations

Maximal Score After Applying K Operations

題目描述：給定整數陣列 nums 和整數 k。每次操作：選一個元素 nums[i]，將其加到分數中，然後將 nums[i] 替換為 ⌈nums[i] / 3⌉（向上取整）。執行恰好 k 次操作，回傳能獲得的最大分數。

解題思路：貪心策略：每次操作應選當前最大的元素，以最大化每步的得分。使用最大堆（max-heap）實作此貪心：

1. 將所有元素加入最大堆。
2. 重複 k 次：取出堆頂最大值 v，加到分數，再將 ⌈v/3⌉ 推入堆中。
3. 回傳總分數。

向上取整可用 (v + 2) / 3 計算（整數運算）。貪心的正確性：每次取最大值不影響其他元素，且替換後的值仍可能再次被選，因此不錯失任何最優機會。

時間複雜度：O(n + k log n) — 建堆需 O(n)，每次操作一次彈出 + 一次推入各為 O(log n)，共 k 次操作。

空間複雜度：O(n) — 堆的大小始終為 n（每次彈出一個再推入一個，總數不變）。

方法一：排序 + 模擬 每次操作後將新值插入正確位置（保持陣列有序），每次取末尾最大值。插入排序需 O(n)，k 次共 O(kn)，比最大堆慢，不適合大規模輸入。

方法二：Treap / 有序多重集合 用 std::multiset（紅黑樹）取代堆，支援 O(log n) 的插入與查最大值。功能更強（可任意刪除），但常數比堆大，本題不需要額外功能，故堆更優。

方法三：暴力模擬 每次線性掃描找最大值，時間 O(kn)。對 k 和 n 均較小的情況可接受，但無法通過本題的規模限制（n, k 最大 10^5）。

1. 若替換規則改為 nums[i] = nums[i] * 2（每次加倍），則問題變成什麼樣？最大分數是否有封閉解？
2. 若每次操作可選擇將元素除以 3（向下取整）或乘以 2，如何設計貪心策略？
3. 若操作次數 k 非常大（趨近無窮），所有元素最終都會收斂到 1（因為 ⌈1/3⌉ = 1），如何快速計算總分數而不需逐步模擬？