算法
(贪心)
假设我们从红色苹果中取出 $a$ 个,从绿色苹果中取出 $b$ 个,从透明苹果中取出 $c$ 个
我们可以得到:
- $x + y = a + b + c$
- $a \leqslant x$
- $b \leqslant y$
注意到,我们不管怎么取,$x+y$ 总是不变的。我们不妨在红苹果中取出前 $x$ 大的苹果,在绿苹果中取出前 $y$ 大的苹果,再取出所有的透明苹果,然后按美味值大小对这些苹果降序排序,取出前 $x + y$ 大的即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
int main() {
int x, y;
cin >> x >> y;
int a, b, c;
cin >> a >> b >> c;
vector<int> p(a), q(b), r(c);
rep(i, a) cin >> p[i];
rep(i, b) cin >> q[i];
rep(i, c) cin >> r[i];
sort(p.rbegin(), p.rend());
sort(q.rbegin(), q.rend());
vector<int> d;
rep(i, x) d.push_back(p[i]);
rep(i, y) d.push_back(q[i]);
rep(i, c) d.push_back(r[i]);
sort(d.rbegin(), d.rend());
ll ans = 0;
rep(i, x + y) ans += d[i];
cout << ans << '\n';
return 0;
}
Python 代码
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p = sorted(p)[::-1]
q = sorted(q)[::-1]
r += p[:x]
r += q[:y]
ans = sum(sorted(r)[::-1][:x+y])
print(ans)
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
r += sorted(p)[-x:]
r += sorted(q)[-y:]
ans = sum(sorted(r)[-(x+y):])
print(ans)