有A个红苹果,美味度分别为p[i];有B个青苹果,美味度分别为q[i];另外还有C个无色苹果,美味度分别为r[i],无色苹果在吃之前可以涂成红色或青色。现在要吃X个红苹果和Y个青苹果,求能吃到的最大美味度。
1<=X<=A<=1E5; 1<=Y<=B<=1E5; 1<=C<=1E5; 1<=p[i],q[i],r[i]<=1E9
反悔贪心,先不考虑无色苹果,按要求吃美味度最大的红苹果和青苹果,放到小根堆里,然后用美味度更大的无色苹果去替换堆里的苹果,使答案更优。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)
const int N = 100005;
int X, Y, A, B, C, p[N], q[N], r[N];
void solve() {
cin >> X >> Y >> A >> B >> C;
rep(i,1,A) cin >> p[i];
rep(i,1,B) cin >> q[i];
rep(i,1,C) cin >> r[i];
sort(p+1,p+1+A, [&](auto &x, auto &y) {return x > y;});
sort(q+1,q+1+B, [&](auto &x, auto &y) {return x > y;});
priority_queue<int,vector<int>,greater<>> pq;
rep(i,1,X) pq.push(p[i]);
rep(i,1,Y) pq.push(q[i]);
rep(i,1,C) {
auto t = pq.top();
if (r[i] > t) {
pq.pop();
pq.push(r[i]);
}
}
int ans = 0;
while (!pq.empty()) {
ans += pq.top();
pq.pop();
}
cout << ans << "\n";
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}
标签:pq,int,auto,rep,苹果,美味,abc160E
From: https://www.cnblogs.com/chenfy27/p/18063998