算法
(优先队列) $O(n\log n)$
可以用大根堆来维护一下 $n$ 张卡牌以及待替换的 $m$ 张卡牌,把 $(数值,个数)$ 捆绑成 $pair$ 来维护,而小根堆的前 $n$ 张卡牌即是我们需要的卡牌,把它们累加进答案即可。
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 std::pair;
using std::make_pair;
priority_queue<pair<int, int>> q;
int main() {
int n, m;
cin >> n >> m;
rep(i, n) {
int a;
cin >> a;
q.push(make_pair(a, 1));
}
rep(i, m) {
int b, c;
cin >> b >> c;
q.push(make_pair(c, b));
}
long long ans = 0;
rep(i, n) {
auto p = q.top();
q.pop();
ans += p.first;
if (p.second > 1) {
p.second--;
q.push(p);
}
}
cout << ans << '\n';
return 0;
}