1962-移除石子使总数最小

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个整数数组 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

方法一：最大堆（优先队列）

提示 1

为了使得操作后剩下的石头最小，我们需要在每次操作时尽可能多地移除石子，即选择石子数量最多的一堆进行操作。

提示 1 解释

我们假设某一步操作没有选择石子数量最多的一堆（记为第 opt 堆）进行操作，而是选择了第 i 堆，那么后续可能有两种情况：

  • 第一种，如果后续的某一步中选择了第 opt 堆，那么我们可以交换这两步的操作，最终剩余的石子数目不变；

  • 第二种，如果后续没有移除过第 opt 堆的石子，那么将从当前开始到结束为止所有选择第 i 堆的操作全部换成第 opt 堆，总移除的石子数目也不会减少。

因此，每次选择石子数量最多的一堆进行操作是最优的。

思路与算法

根据 提示 1，每一次「移除石子」的操作可以被拆分为两个部分：

  • 从石子堆中寻找到最大值；

  • 将该值进行修改。

假设石子堆数组 piles 的长度为 n，那么单次操作的时间复杂度为 O(n)，无法通过本题。因此我们可以将「移除石子」操作的两个部分进行如下修改：

  • 从石子堆中记录并弹出最大值；

  • 将该值进行修改，并重新添加至石子堆中。

同时寻找一个可以在较好的时间复杂度下实现「查询并移除最大值」与「插入元素」的数据结构。

我们可以用一个最大堆实现的优先队列来维护石子堆数组 piles，它可以在 O(\log n) 的时间复杂度下实现「查询并移除最大值」与「插入元素」这两个操作。

每一次操作时，我们首先记录并弹出 piles 中的最大值 tmp，随后从中减去 \lfloor \textit{tmp} / 2 \rfloor（其中 \lfloor \dots \rfloor代表向下取整），并将修改后的值添加进 piles 中。当进行 k 次操作后，我们计算 piles 中各元素之和，并返回作为答案。

需要注意的是，C++ 的二叉堆默认为最大堆，但Python 的二叉堆默认为最小堆，因此我们需要将 piles 中的每个元素取相反数然后进行操作，并对求和后的结果再次取相反数作为答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        // 生成最大堆
        make_heap(piles.begin(), piles.end());
        for (int i = 0; i < k; ++i){
            // 单次操作：记录并弹出最大值，修改后重新添加进堆
            pop_heap(piles.begin(), piles.end());
            piles.back() -= piles.back() / 2;
            push_heap(piles.begin(), piles.end());
        }
        return accumulate(piles.begin(), piles.end(), 0);
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        n = len(piles)
        # 生成最大堆
        for i in range(n):
            piles[i] = -piles[i]
        heapq.heapify(piles)
        for i in range(k):
            # 单次操作：记录并弹出最大值，修改后重新添加进堆
            tmp = heapq.heappop(piles)
            heapq.heappush(piles, tmp + (-tmp) // 2)
        return -sum(piles)

复杂度分析

  • 时间复杂度：O(n + k\log n)，其中 n 为 piles 的长度。建堆与计算结果的复杂度为 O(n)；每次弹出最大值与添加新值的时间复杂度为 O(\log n)，共需进行 k 次。

  • 空间复杂度：O(1)。

 Comments
On this page
1962-移除石子使总数最小