class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
}
};
1962. 移除石子使总数最小
给你一个整数数组 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 <= 1051 <= piles[i] <= 1041 <= k <= 105原站题解
javascript 解法, 执行用时: 1816 ms, 内存消耗: 72.7 MB, 提交时间: 2023-12-23 00:11:26
/**
* @param {number[]} piles
* @param {number} k
* @return {number}
*/
var minStoneSum = function(piles, k) {
const pq = new MaxPriorityQueue();
for (const pile of piles) {
pq.enqueue(pile, pile);
}
for (let i = 0; i < k; i++) {
let pile = pq.front().element;
pq.dequeue();
pile -= Math.floor(pile / 2);
pq.enqueue(pile, pile);
}
let sum = 0;
while (!pq.isEmpty()) {
sum += pq.front().element;
pq.dequeue();
}
return sum;
};
python3 解法, 执行用时: 628 ms, 内存消耗: 28.5 MB, 提交时间: 2023-12-23 00:10:56
class Solution:
def minStoneSum(self, piles: List[int], k: int) -> int:
heap = [-a for a in piles]
heapify(heap)
for i in range(k):
a = -heappop(heap)
a = a - a//2
heappush(heap, -a)
return -sum(heap)
java 解法, 执行用时: 339 ms, 内存消耗: 55 MB, 提交时间: 2023-09-22 10:35:15
class Solution {
public int minStoneSum(int[] piles, int k) {
// 大根堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int n : piles) {
priorityQueue.add(n);
}
while (k > 0 && !priorityQueue.isEmpty()) {
// 当前数组最大值
int pop = priorityQueue.poll();
// 最大值减去自身的一半放入大根堆
int temp = pop - (pop >> 1);
priorityQueue.add(temp);
k--;
}
return priorityQueue.stream().reduce(Integer :: sum).get();
}
public int minStoneSum2(int[] piles, int k) {
int sum = 0;
// lambda表达式实现最大堆优先队列
Queue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
// 队列初始化，数组每个元素入队
for (int pile : piles) {
priorityQueue.offer(pile);
}
// 移除石子操作
for (int i = 0; i < k; i++) {
// 在对堆移除Math.floor(x)石子之后剩余的石子入队
// Math.floor(x)函数是向下取整
priorityQueue.offer(priorityQueue.poll() - (int) Math.floor(priorityQueue.poll() / 2));
}
// 计算最后的和
while (priorityQueue.size() >= 1){
sum += priorityQueue.poll();
}
return sum;
}
}
python3 解法, 执行用时: 864 ms, 内存消耗: 27.3 MB, 提交时间: 2023-09-22 10:34:28
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)
cpp 解法, 执行用时: 388 ms, 内存消耗: 92.6 MB, 提交时间: 2023-09-22 10:34:11
// 最大堆
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);
}
};
cpp 解法, 执行用时: 236 ms, 内存消耗: 100.9 MB, 提交时间: 2023-09-22 10:33:48
class Solution {
public:
//
int minStoneSum(vector<int>& piles, int k)
{
// 首先将原数组排序
sort(piles.begin() , piles.end());
// 使用队列来储存被扔掉过的石头
queue<int> q;
// 指向原有石头的末尾，当它前移时代表之前的元素被删除。当然直接pop_back也是可以的。
auto now = piles.rbegin();
// 当前最大的石头和剩余石头总和
int tmp , ans = 0;
for(auto i : piles)
ans += i;
while(k--)
{
// 若还未扔过石头或原有石头的最大值大于被扔过石头的最大值时，需要扔掉原有石头里最大的，也就是now指向的那堆
// 将反向迭代器now前移，表示这对石头被扔掉了
if(q.empty() || (!q.empty() && now != piles.rend() && *now > q.front()))
tmp = *now++;
// 否则将要扔掉的石头应该位于队列的头部，将它出队
else
{
tmp = q.front();
q.pop();
}
// 将取出的石头扔掉一半后加入队列，并在总和里扣除扔掉的部分
q.push(tmp - tmp / 2);
ans -= tmp / 2;
}
return ans;
}
// 类似于桶排序+单调指针的方式来模拟取出的过程
int minStoneSum2(vector<int>& piles, int k)
{
int ans = 0;
int s[10010] = {0};
for(auto i : piles)
{
s[i]++;
ans += i;
}
for(int i = 10000 , j ; k > 0 ; k-- , i = j)
{
for(j = i ; s[j] == 0 ; j--);
ans -= j / 2;
s[j] --;
s[j - j / 2] ++;
}
return ans;
}
};
golang 解法, 执行用时: 460 ms, 内存消耗: 8.7 MB, 提交时间: 2023-09-22 10:31:35
// 每次取最大元素，用最大堆维护
func minStoneSum(piles []int, k int) (ans int) {
h := &hp{piles}
heap.Init(h)
for ; k > 0; k-- {
h.IntSlice[0] -= h.IntSlice[0] / 2
heap.Fix(h, 0)
}
for _, v := range h.IntSlice {
ans += v
}
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 }