免费创办网站,wordpress08模板,网架提升公司,网页布局设计说明1. 题意
给定一个数组#xff0c;每次从中取走最大的数#xff0c;返回开根号向下取整送入堆中#xff0c;最后计算总和。
从数量最多的堆取走礼物
2. 题解
直接用堆模拟即可
2.1 我的代码
用了额外的空间O( n ) priority_queue会自动调用make_heap() 、pop_heap()
c…1. 题意
给定一个数组每次从中取走最大的数返回开根号向下取整送入堆中最后计算总和。
从数量最多的堆取走礼物
2. 题解
直接用堆模拟即可
2.1 我的代码
用了额外的空间O( n ) priority_queue会自动调用make_heap() 、pop_heap()
class Solution {
public:long long pickGifts(vectorint gifts, int k) {priority_queueint, vectorint, 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(vectorint gifts, int k) {make_heap(gifts.begin(), gifts.end(), lessint());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 );}
};
