2530-执行 K 次操作后的最大分数

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步 操作 中：

1. 选出一个满足 0 <= i < nums.length 的下标 i ，
2. 将你的 分数 增加 nums[i] ，并且
3. 将 nums[i] 替换为 ceil(nums[i] / 3) 。

返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

示例 1：

**输入：** nums = [10,10,10,10,10], k = 5
**输出：** 50
**解释：** 对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。

示例 2：

**输入：** nums = [1,10,3,3,3], k = 3
**输出：** 17
**解释：** 可以执行下述操作：
第 1 步操作：选中 i = 1 ，nums 变为 [1, _ **4**_ ,3,3,3] 。分数增加 10 。
第 2 步操作：选中 i = 1 ，nums 变为 [1, _ **2**_ ,3,3,3] 。分数增加 4 。
第 3 步操作：选中 i = 2 ，nums 变为 [1,1, _ **1**_ ,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。

提示：

• 1 <= nums.length, k <= 105
• 1 <= nums[i] <= 109

视频讲解 ，欢迎点赞~

---

用一个最大堆模拟，每次循环累加堆顶，同时修改堆顶。

原地修改可以做到 O(1) 空间复杂度。

[sol1-Python3]

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        for i in range(len(nums)):
            nums[i] = -nums[i]  # 最大堆
        heapify(nums)
        ans = 0
        for _ in range(k):
            ans -= heapreplace(nums, nums[0] // 3)
        return ans

[sol1-Go]

func maxKelements(nums []int, k int) (ans int64) {
	h := hp{nums}
	heap.Init(&h)
	for ; k > 0; k-- {
		ans += int64(h.IntSlice[0])
		h.IntSlice[0] = (h.IntSlice[0] + 2) / 3
		heap.Fix(&h, 0)
	}
	return
}

type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (hp) Push(interface{})     {}
func (hp) Pop() (_ interface{}) { return }

复杂度分析

• 时间复杂度：O(k\log n)，其中 n 为 nums 的长度。
• 空间复杂度：O(1)，仅用到若干额外变量。