题目来源：牛客
除2！
题目描述：
给一个数组，一共有 n 个数。
你能进行最多 k 次操作。每次操作可以进行以下步骤：
· 选择数组中的一个偶数 ai ，将其变成 ai / 2 。
现在你进行不超过 k 次操作后，让数组中所有数之和尽可能小。请输出这个最小的和。
输入描述：
第一行输入两个正整数 n 和 k，用空格隔开
第二行输入 n 个正整数 ai
数据范围：
1 ≤ n ≤ 100000 , 1 ≤ k ≤ 109
1 ≤ ai ≤ 109
输出描述：
一个正整数，代表和的最小值。
示例1
输入：5 3
2 4 8 10 11
输出：24
说明：对8操作2次，对10操作1次，最后的数组是2 4 2 5 11。可以证明这样的操作是最优的。
解析
要使最后的结果最小，我们可以每次对最大的那个偶数进行除2操作，这样可以保证每次操作都是最优解，最终的结果就能保证最小。我们可以使用大根堆（优先队列）来存储偶数，一定是偶数，因为奇数是不参与操作的。每次对堆顶的元素进行除2操作，如果还是偶数则放回到堆中，如果不是偶数则不放回。当堆中没有元素或者操作次数用完时，得到的结果就是最终答案。
因为我们要对数组求和，而数组中的元素可以达到 109 ，并且个数也能达到 105 所以我们要对答案开 long long。
代码实现
#include<iostream>
#include<queue>
using namespace std;long long n, k, sum;
priority_queue<long long> pq;int main()
{cin >> n >> k;// 临时变量用来接收输入int tmp = 0;while (n--){cin >> tmp;sum += tmp;// 偶数入堆if (tmp % 2 == 0){pq.push(tmp);}}// 还有偶数可以操作并且还有操作次数while (pq.size() && k--){// 取出堆顶元素（最大的偶数）并除2操作long long x = pq.top() / 2;pq.pop();// 总和减少sum -= x;// 除2后还是偶数则需要再次入堆if (x % 2 == 0){pq.push(x);}}cout << sum;return 0;
}
