Leetcode1962. 移除石子使总数最小-优先队列_移出石子使总数最小 leetcode

链接:https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total/

解题思路:

• 从题中可以看出这个floor函数实际上就是数量的一半的意思,本题每一次移除某一堆石子的一半,所以为了剩下的石子总数最小,我们每一次都要对石子数量最多的进行减半操作,所以每一次都要返回最大的值,这里就需要构建大顶堆
• 注意:
  1.大顶堆构建
  2.堆的弹出和压入操作

class Solution {
public:
	int minStoneSum(vector<int>& piles, int k) {
        // 默认创建大顶堆priority_queue<int>mqueue;
		priority_queue<int,vector<int>,less<int>>mqueue;
		for (int i : piles) {
			mqueue.emplace(i);
		}
        // 使用堆存储能够很好的保证每一次取到的都是最大的
		for (int i = 0; i < k; ++i) {
			int temp = mqueue.top();
			mqueue.pop();
			mqueue.emplace(temp - temp / 2);
		}
		int ans = 0;
        // 遍历堆中元素
		while (!mqueue.empty()) {
			ans += mqueue.top();
			mqueue.pop();
		}
		return ans;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23