链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

给一个数组，一共有 n n\ n 个数。
你能进行最多 k k\ k 次操作。每次操作可以进行以下步骤：

• 选择数组中的一个偶数 aia_iai​，将其变成 ai/2a_i/2ai​/2 。

现在你进行不超过 k k\ k 次操作后，让数组中所有数之和尽可能小。请输出这个最小的和。

思路：

遍历一遍数组，偶数保存在一个大堆中，奇数直接加在结果中。然后每次从堆顶提取元素，即当前最大的偶数，对其除以2，若是奇数则直接加入结果中，若是偶数则重新放入大堆中。

注意:本题结果可能超过INT的范围，因此用long long。

#include<algorithm>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>using namespace std;struct cmp
{bool operator()(int a,int b){return a<b;}
};int main(){ int n,k;cin>>n>>k;priority_queue<int,vector<int>,cmp>qn;long long ret=0;for(int i=0;i<n;i++){int kk=0;cin>>kk;if(kk%2==0)qn.push(kk);elseret+=kk;}while(k--&&qn.size()){int kk=qn.top()/2;qn.pop();if(kk%2==0)qn.push(kk);elseret+=kk;}while(qn.size()){ret+=qn.top();qn.pop();}cout << ret;return 0;
}