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

标签: 贪心 数组 堆（优先队列）

难度: Medium

给你一个下标从 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,2,1,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。

提示：

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

Submission

运行时间: 156 ms

内存: 31.2 MB

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        r = 0
        while k > 0:
            nums.sort()
            index = 0
            target = math.ceil(nums[-1] / 3)
            while nums[index] < target:
                index += 1
            result = nums[index:]
            if len(result) >= k:
                r += sum(result[-k:])
                return r
            nums = nums[:index]
            r += sum(result)
            for ele in result:
                nums.append(math.ceil(ele / 3))
            k -= len(result)

Explain

该题解通过贪心算法的方式寻找在每一步操作中可以获得最大分数的策略。具体步骤如下：1. 对数组进行排序。2. 找到数组中第一个大于等于最大值三分之一的位置（确保选择最大值是最优的）。3. 根据剩余操作次数k，比较这个位置到数组末尾的元素数量与k的大小。如果足够，直接将这些元素累加到结果中并返回。否则，更新数组和分数，继续下一轮循环。在更新数组时，将选择的元素替换为其三分之一向上取整后的结果。

时间复杂度: O(k * n log n)

空间复杂度: O(n)

# 类定义

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        r = 0  # 初始化结果变量为0
        while k > 0:  # 当还有操作次数时执行循环
            nums.sort()  # 对数组进行排序
            index = 0  # 初始化索引变量
            target = math.ceil(nums[-1] / 3)  # 计算最大元素三分之一的向上取整
            while nums[index] < target:  # 找到第一个大于等于target的元素的索引
                index += 1
            result = nums[index:]  # 从index到数组末尾的元素将被处理
            if len(result) >= k:  # 如果剩余元素数量足够完成剩余操作
                r += sum(result[-k:])  # 只累加需要的k个元素到结果中
                return r
            nums = nums[:index]  # 更新数组为未处理的部分
            r += sum(result)  # 累加本轮处理的结果到总分
            for ele in result:  # 更新被处理的元素值
                nums.append(math.ceil(ele / 3))
            k -= len(result)  # 减少相应的操作次数

Explore

在算法中选择先对数组进行排序是为了方便快速地找到大于或等于最大元素三分之一的元素。排序后，数组从小到大排列，这样可以通过索引快速访问到任何一个元素，尤其是较大的元素。这是因为处理较大的元素通常能获得更高的分数，而排序后可以更有效地定位这些元素，并对它们进行操作。此外，排序也使得能够直接应用贪心策略，即从最大的元素开始处理，确保每一步操作都尽可能地获得最大分数。

计算最大元素的三分之一向上取整是为了在每次操作中尽可能地减少元素的值，同时保证这一减少过程在分数上的损失最小。这个操作保证了即使元素值被减少，也是在当前元素值能够提供的范围内最小的损失。这种方式结合贪心策略，即优先处理大的元素，可以确保每次操作都能从剩余的元素中获取到相对最大的分数，从而在整体上最大化最终的总分数。

找到第一个大于等于最大元素三分之一的元素后，直接考虑这个位置到数组末尾的元素是因为这些元素都是相对较大的元素，根据贪心算法的策略，这些元素的处理能够带来更高的分数。处理这些元素的逻辑基于贪心原则，即在每一步都选择当前可以获得最高分数的操作。由于这些元素是从最大元素三分之一的值开始的，它们在接下来的操作中的分数潜力比数组中更小的元素要大，因此优先处理这些元素可以有效地提升总分数。

如果在某一轮操作中，从找到的大于等于最大元素三分之一的位置到数组末尾的元素数量少于剩余操作次数（k），那么算法会先处理这些元素，即将它们的值分别更新为原来的三分之一向上取整后的值，并将这些更新后的值重新放回数组中。同时，这一轮操作的分数（这些元素的总和）会被累加到最终结果中。接着，减少操作次数k，继续对更新后的数组进行排序和处理，直到操作次数用完。这样的处理确保了即使元素数量不足，也能尽可能地利用现有的元素值，进行更多的操作来积累分数。