🔗 🟡 2530. Maximal Score After Applying K Operations 1386

tags: `Weekly Contest 327` `陣列(Array)` `貪心(Greedy)` `堆積(Heap)`

題意

給定一個下標從 $0$ 開始的整數陣列 $nums$ 和一個整數 $k$ 。你的 起始分數 為 $0$ 。

在每次操作中：

選擇一個索引 $i$ 使得 $0 \leq i < nums.length$ ，
將你的分數增加 $nums[i]$ ，並且
將 $nums[i]$ 替換為 $\lceil nums[i] / 3 \rceil$ 。

返回在恰好執行 $k$ 次操作後你能獲得的最大可能分數。

向上取整函數 $\lceil val \rceil$ 是不小於 $val$ 的最小整數。

約束條件

$1 \leq nums.length, k \leq 10^5$
$1 \leq nums[i] \leq 10^9$

思路：貪心(Greedy) + 堆積(Heap)模擬

為了獲得最大可能分數，我們可以基於貪心(Greedy) 思路，每次選擇當前陣列中最大的元素進行操作。

而為了快速獲取當前陣列中最大的元素，我們可以使用堆積(Heap) ，透過維護一個最大堆積(Max Heap) 使得我們可以快速獲取當前最大的元素。

在每次操作時，我們將當前最大的元素取出，並將其加入到總分中，然後將其替換為 $\lceil \frac{x}{3} \rceil$ ，並將其重新插入堆積中。

值得注意的是，由於 $x$ 為整數，因此 $\lceil \frac{x}{3} \rceil$ 等價於 $\lfloor \frac{x + 2}{3} \rfloor$ ，即 $\frac{x + 2}{3}$ 的整數部分。

此外，Python 中的 heapq 會維護一個最小堆積，因此我們需要將元素取反，以維護一個最大堆積。

複雜度分析

時間複雜度： $\mathcal{O}(n + k \log n)$ $O (n + k lo g n)$ ，其中 $n$ $n$ 為陣列長度。
- 初始化堆積需要 $\mathcal{O}(n)$ 的時間複雜度。
- 每次操作需要 $\mathcal{O}(\log n)$ 的時間複雜度，總共執行 $k$ 次。
空間複雜度： $\mathcal{O}(n)$ $O (n)$ ，其中 $n$ $n$ 為陣列長度。
- 需要額外的 $\mathcal{O}(n)$ 空間來維護堆積。

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        hp = [-x for x in nums]
        heapify(hp)
        ans = 0
        for _ in range(k):
            x = -heappop(hp)
            ans += x
            # heappush(hp, -math.ceil(x / 3))
            heappush(hp, -((x + 2) // 3))
        return ans

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<int> hp(nums.begin(), nums.end());
        long long ans = 0;
        for (int i = 0; i < k; i++) {
            int x = hp.top();
            hp.pop();
            ans += x;
            // hp.push(ceil(x / 3.0));
            hp.push((x + 2) / 3);
        }
        return ans;
    }
};