牛客网 除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=2if (t % 2 == 0) heap.push(t);}cout << sum << endl;return 0;
}