# LeetCode 2530. Maximal Score After Applying K Operations

https://leetcode.com/problems/maximal-score-after-applying-k-operations/description/

## 題目大意

給定整數陣列 `nums` 和整數 `k`，起始分數為 `0`

定義在一次操作中會進行：
1. 選擇一個索引 `i`，滿足 `0 <= i < nums.length`
2. 將 `nums[i]` 加到分數上
3. 將 `nums[i]` 替換為 `ceil(nums[i] / 3)`

回傳進行 `k` 次操作後的最大得分

## 思考

這題一看就知道使用貪婪策略解題即可

每次用 max heap 挑出最大的 `nums[i]`

以下為 C++ 參考答案：

class Solution
{
public:
    long long maxKelements(vector<int> &nums, int k)
    {
        long long ans = 0;
        priority_queue<int> maxHeap(nums.begin(), nums.end());

        while (k--)
        {
            const int maxVal = maxHeap.top();
            maxHeap.pop();
            ans += maxVal;
            maxHeap.push((maxVal + 2) / 3);
        }

        return ans;
    }
};

***

以下為 Go 參考答案：

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(val interface{}) {
	*h = append(*h, val.(int))
}
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	maxVal := old[n-1]
	*h = old[:n-1]
	return maxVal
}

func maxKelements(nums []int, k int) int64 {
	h := &MaxHeap{}
	heap.Init(h)

	for _, num := range nums {
		heap.Push(h, num)
	}

	var ans int64

	for k > 0 {
		k--
		maxVal := heap.Pop(h).(int)
		ans += int64(maxVal)
		heap.Push(h, (maxVal+2)/3)
	}

	return ans
}

之前我不知道怎麼在 Go 用 priority queue
我後來了解到 Go 標準庫有 `"container/heap"`
[](https://emoji.gg/emoji/48301-clownpepe)