[LeetCode] 1962. Remove Stones to Minimize the Total

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:
Choose any piles[i] and remove floor(piles[i] / 2) stones from it.
Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

Example 1:
Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:

  • Apply the operation on pile 2. The resulting piles are [5,4,5].
  • Apply the operation on pile 0. The resulting piles are [3,4,5].
    The total number of stones in [3,4,5] is 12.

Example 2:
Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:

  • Apply the operation on pile 2. The resulting piles are [4,3,3,7].
  • Apply the operation on pile 3. The resulting piles are [4,3,3,4].
  • Apply the operation on pile 0. The resulting piles are [2,3,3,4].
    The total number of stones in [2,3,3,4] is 12.

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

移除石子使总数最小。

给你一个整数数组 piles ,数组 下标从 0 开始 ,其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ,请你执行下述操作 恰好 k 次:
选出任一石子堆 piles[i] ,并从中 移除 floor(piles[i] / 2) 颗石子。
注意:你可以对 同一堆 石子多次执行此操作。
返回执行 k 次操作后,剩下石子的 最小 总数。
floor(x) 为 小于 或 等于 x 的 最大 整数。(即,对 x 向下取整)。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

思路是贪心。这里我们需要借助一个优先队列构建的最大堆,将每一堆的石子数加入最大堆,并同时记录石子的总数,记为 sum。每次弹出堆顶的元素并除以 2,同时记得把减去的部分从 sum 中减去。这样最后 sum 就是全局剩下的石子总数。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
int sum = 0;
for (int p : piles) {
sum += p;
queue.offer(p);
}

int res = 0;
while (!queue.isEmpty() && k != 0) {
int top = queue.poll();
int remove = top / 2;
res += remove;
queue.offer(top - remove);
k--;
}
return sum - res;
}
}

[LeetCode] 1962. Remove Stones to Minimize the Total
https://shurui91.github.io/posts/3274119760.html
Author
Aaron Liu
Posted on
August 16, 2021
Licensed under