1. 題意
給定一個數(shù)組，每次從中取走最大的數(shù)，返回開根號向下取整送入堆中，最后計(jì)算總和。
從數(shù)量最多的堆取走禮物
2. 題解
直接用堆模擬即可
2.1 我的代碼
用了額外的空間O( n )priority_queue會自動調(diào)用make_heap() 、pop_heap()文章來源：http://www.zghlxwxcb.cn/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 更簡的代碼
直接在原數(shù)組上建堆就可以了文章來源地址http://www.zghlxwxcb.cn/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 );
}
};
到了這里，關(guān)于leetcode_2558 從數(shù)量最多的堆取走禮物的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
