题目来源：牛客
除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; }
