蓝桥杯备考数据结构堆之-除2
目录
蓝桥杯备考：数据结构堆之 除2！
这道题我们可以用优先级队列来解决，我们的算法思路如下：
先把n个数的和加起来 并把是偶数的值插入到优先级队列里面
接下来如果队列有值并且你还有操作次数，你就不断的把最大的偶数除2，并且判断除2的结果是不是偶数，如果是偶数继续插入到堆里面
#include <iostream>
#include <queue>
typedef long long ll;
using namespace std;
ll sum;
ll n,k;
priority_queue <int> heap;
int main()
{
cin >> n >> k;
ll x;
for(int i = 1;i<=n;i++)
{
cin >> x;
sum+=x;
if(x%2 == 0) heap.push(x);
}
while(k--&&heap.size())
{
ll t = heap.top();heap.pop();
sum-=t;
t/=2;
if(t%2==0) heap.push(t);
sum+=t;
}
cout << sum << endl;
return 0;
}