移除石子使总数最小

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

难度: Medium

给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：

  • 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。

注意：你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后，剩下石子的 最小 总数。

floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。

示例 1：

输入：piles = [5,4,9], k = 2
输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。
剩下石子的总数为 12 。

示例 2：

输入：piles = [4,3,6,7], k = 3
输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。
- 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。
剩下石子的总数为 12 。

提示：

  • 1 <= piles.length <= 105
  • 1 <= piles[i] <= 104
  • 1 <= k <= 105

Submission

运行时间: 116 ms

内存: 26.8 MB

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        tot, cnt, mul, reduce = 0, [0] * 10001, 0, 0
        for x in piles:
            tot, cnt[x] = tot + x, cnt[x] + 1
        for i in range(10000, 0, -1):
            if not cnt[i]: continue
            mul = min(cnt[i], k)
            reduce = i // 2
            tot -= reduce * mul
            cnt[i - reduce] += mul
            k -= mul
            if not k: break
        return tot

Explain

题解采用了计数排序的方法来处理问题，以达到较高的效率。首先，算法通过遍历石子堆数组 'piles' 来统计每种石子数量的堆数，同时计算所有石子的总数。接着，从石子数量最大的堆开始，尽可能多地执行移除操作，直到操作次数 'k' 耗尽或没有可以移除的石子堆为止。具体来说，每次从最大的石子堆中减去 'floor(i / 2)' 的石子，更新总数，并递减操作次数 'k'。该方法通过优先移除最多的石子来确保剩余石子总数最小。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义 Solution 类

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        tot, cnt, mul, reduce = 0, [0] * 10001, 0, 0  # 初始化总石子数、计数数组、多余变量
        for x in piles:  # 统计石子总数和每种石子数量的堆数
            tot, cnt[x] = tot + x, cnt[x] + 1
        for i in range(10000, 0, -1):  # 从最大的石子数量开始减少
            if not cnt[i]: continue  # 如果当前数量的石子堆数为0，跳过
            mul = min(cnt[i], k)  # 计算此数量石子堆可以进行的最大移除次数
            reduce = i // 2  # 计算每次操作可以移除的石子数
            tot -= reduce * mul  # 更新总石子数
            cnt[i - reduce] += mul  # 更新新数量的石子堆数
            k -= mul  # 减少剩余可操作次数
            if not k: break  # 如果操作次数用尽，结束循环
        return tot  # 返回剩余石子的总数

Explore

该算法假设石子的最大数量不超过10000。这种假设可能基于题目的数据限制或实际应用场景中石子数量的常见范围。固定计数数组的大小为10001（从0到10000）是为了直接使用石子数量作为索引，便于快速访问和更新对应石子堆的数量。如果石子数量能超过10000，这种方法就会导致数组越界错误。

从最大的石子数量开始减少是为了尽可能效率地减少总石子数量。每次操作都会移除堆中石子数量的一半（向下取整），因此从较大的堆开始移除可以更快地减少总石子数。这种策略是贪心算法的一种表现，旨在每步操作中取得最大的减少效果。

当`reduce`的计算结果为0时（例如`i`为1时），该次操作实际上没有减少任何石子，这确实会影响算法的效率。在实际执行中，如果`reduce`为0，应该跳过该步操作，因为它不会改变石子的总数。这种情况可以通过在操作前检查`reduce`是否为0来优化，避免无效操作，从而提高算法的整体效率。

在原算法中，`i - reduce`可能会产生负索引，尤其是当`i`较小时。例如，如果`i`为1且`reduce`同样为1，则`i - reduce`为0，不会产生负索引，但接近边界。为确保不产生负索引，应在更新计数数组前检查`i - reduce`是否大于等于0。在实际实现中，可以通过设置`reduce = min(i // 2, i)`来确保`i - reduce`始终非负。这样的修改不仅防止了负索引的出现，也确保了算法的安全和稳定。