牛客网 除2！（详解）c++
题目链接：除2！
1.题目解析
1：想让数组所有数之和尽可能小，肯定有个想法，就是我每次选数组中偶数的时候，我必定挑一个最大的，因为我挑一个最大的出来，把它变成一半，这个时候总和减小肯定是最多的
2：我们待会儿是要求所有数组元素的和，数据量有100,000这么大，每个数有10的九次方这么大，有可能超出int的范围，所以我们要用long long来存这个数，看到数据范围的时候，大家一定要小心一点，我们是用int还是用long long
结合示例：最多进行三次操作，把10变成5，接下来最大的值是8，把8变成4，这两个4随便挑一个出来变成2，这时它们的加起来是2+4+2+5+11=24
2.算法原理
解法：每次挑选出，当前数组中最大的偶数，然后减小一半，利用大根堆实现
代码：
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
int n, k;
priority_queue<int> heap; //默认是大根堆
int main()
{
cin >> n >> k;
LL sum = 0;
for (int i = 1; i <= n; ++i)
{
int x; cin >> x;
sum += x;
//偶数进堆
if (x % 2 == 0) heap.push(x);
}
while (heap.size() && k--)
{
int t = heap.top() / 2;
heap.pop();
sum -= t;
//除完后可能还是偶数
//用%不用除，比如10/2=5,5/2=2
if (t % 2 == 0) heap.push(t);
}
cout << sum << endl;
return 0;
}