算法

(贪心、优先队列) $O(M\log N)$

我们可以把現阶段的最大值除以 $2$， 直到抵扣券用完。对于现阶段的 $\max$ 我们可以用 std::priority_queue 来找。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::priority_queue;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;

    priority_queue<int> q;
    rep(i, n) {
        int a;
        cin >> a;
        q.push(a);
    }

    rep(i, m) {
        int a = q.top(); q.pop();
        q.push(a / 2);
    }

    ll ans = 0;
    rep(i, n) {
        ans += q.top(); q.pop();
    }

    cout << ans << '\n';

    return 0;
}