leetcode_2558 从数量最多的堆取走礼物
1. 题意
给定一个数组，每次从中取走最大的数，返回开根号向下取整送入堆中，最后计算总和。
从数量最多的堆取走礼物
2. 题解
直接用堆模拟即可
2.1 我的代码
用了额外的空间O( n )
priority_queue会自动调用make_heap() 、pop_heap()
class Solution {
public:long long pickGifts(vector<int>& gifts, int k) {priority_queue<int, vector<int>, less<> > maxHeap(gifts.begin(), gifts.end());long long ans = 0;for ( int i = 0; i < k; ++i) {int p = maxHeap.top();if (p == 1) break;maxHeap.pop();maxHeap.push( (int) sqrt(p));}while (!maxHeap.empty()) {ans += maxHeap.top();maxHeap.pop();}return ans;}
};
2.2 更简的代码
直接在原数组上建堆就可以了
class Solution {
public:long long pickGifts(vector<int>& gifts, int k) {make_heap(gifts.begin(), gifts.end(), less<int>());for ( int i = 0; i < k; ++i) {pop_heap(gifts.begin(), gifts.end() );gifts.back() = sqrt(gifts.back());push_heap(gifts.begin(), gifts.end());}return accumulate(gifts.begin(), gifts.end(), 0ll );}
};