題目描述:給定整數陣列 nums 和整數 k。每次操作:選一個元素 nums[i],將其加到分數中,然後將 nums[i] 替換為 ⌈nums[i] / 3⌉(向上取整)。執行恰好 k 次操作,回傳能獲得的最大分數。
解題思路:貪心策略:每次操作應選當前最大的元素,以最大化每步的得分。使用最大堆(max-heap)實作此貪心:
v,加到分數,再將 ⌈v/3⌉ 推入堆中。向上取整可用 (v + 2) / 3 計算(整數運算)。貪心的正確性:每次取最大值不影響其他元素,且替換後的值仍可能再次被選,因此不錯失任何最優機會。
時間複雜度:O(n + k log n) — 建堆需 O(n),每次操作一次彈出 + 一次推入各為 O(log n),共 k 次操作。
空間複雜度:O(n) — 堆的大小始終為 n(每次彈出一個再推入一個,總數不變)。
1. Build max-heap H from all elements of nums. 2. Initialize score = 0. 3. Repeat k times: a. v = H.top(); pop H. b. score += v. c. Push (v + 2) / 3 into H. 4. Return score.
方法一:排序 + 模擬 每次操作後將新值插入正確位置(保持陣列有序),每次取末尾最大值。插入排序需 O(n),k 次共 O(kn),比最大堆慢,不適合大規模輸入。
方法二:Treap / 有序多重集合
用 std::multiset(紅黑樹)取代堆,支援 O(log n) 的插入與查最大值。功能更強(可任意刪除),但常數比堆大,本題不需要額外功能,故堆更優。
方法三:暴力模擬 每次線性掃描找最大值,時間 O(kn)。對 k 和 n 均較小的情況可接受,但無法通過本題的規模限制(n, k 最大 10^5)。
nums[i] = nums[i] * 2(每次加倍),則問題變成什麼樣?最大分數是否有封閉解?