1. 题意
给定一个数组，每次从中取走最大的数，返回开根号向下取整送入堆中，最后计算总和。
从数量最多的堆取走礼物
2. 题解
直接用堆模拟即可
2.1 我的代码
用了额外的空间O( n )priority_queue会自动调用make_heap() 、pop_heap()文章来源：https://www.toymoban.com/news/detail-737785.html
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 更简的代码
直接在原数组上建堆就可以了文章来源地址https://www.toymoban.com/news/detail-737785.html
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 );
}
};
到了这里，关于leetcode_2558 从数量最多的堆取走礼物的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
