牛客挑战赛45 除2！题解

思路：模拟

根据题意，我们需要在不多于 次操作中，每次选择尽可能大的偶数，将其减少为原来的一半，从而使全局元素和 降低，由于需要动态存储数组元素并维护其最大值，所以利用优先队列 ，将所有元素放入优先队列，并维护一个变量 记录元素值为偶数的个数，每次选择一个偶数并降为一半后，判断新得到数值的奇偶性，并更新值，防止在 次操作中，数组中已经没有偶数元素。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
typedef long long ll;

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<int> q;
    ll sum = 0;    // 维护全局元素和时，因为元素范围较大，所以用long long型
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
        cnt += (a[i] % 2 == 0);
        q.push(a[i]);
    }
    while(!q.empty() && k && cnt) {
        while(!q.empty() && q.top() % 2 != 0) {
            q.pop();
        }
        if(q.empty()) break;
        int x = q.top();
        q.pop();
        x /= 2;
        //cout << x << " " << sum << endl;
        cnt -= (x % 2 != 0);
        sum -= x;
        k--;
        q.push(x);
    }
    cout << sum;
}

复杂度分析

时间复杂度：，优先队列动态维护数组复杂度为
空间复杂度：，利用了优先队列存储元素