蓝桥杯备考:数据结构堆之 除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;
}