题解 AT2672 【Coins】
Kewth
2019-12-25 12:05:22
提供一个用排序 + 优先队列的做法。
首先默认将三元组 $(a, b, c)$ 替换为二元组 $(e=b-a, f=c-a)$ （先默认所有人拿金币）。
然后问题转换为在 $n$ 个二元组中选 $y$ 个获得 $e$ 收益，选 $z$ 个获得 $f$ 收益，最大化总收益。
对于两个二元组 $(e_i, f_i)$, $(e_j, f_j)$ 假设 $i$ 选 $f$ 且 $j$ 选 $e$ ，
考虑什么时候交换他们的选择收益不会变少，也就是 $e_i + f_j \geq e_j + f_i$ ，
移项得 $e_i - f_i \geq e_j - f_j$ ，那么通过排序使得二元组按 $e - f$ 单调不降，
就有对于任意 $i < j$ ，如果 $i$ 选 $f$ 且 $j$ 选 $e$ ，那么交换两者状态一定不会变差。
换言之，存在最优解满足选 $e$ 的全在选 $f$ 的左边，
也就是说存在一个 $k$ 使得有最优解在 1 到 $k$ 中取 $y$ 个 $e$ 在 $k + 1$ 到 $n$ 中取 $z$ 个 $f$ 。
那么只需要通过优先队列预处理出每个前缀前 $y$ 大的 $e$ 的和以及每个后缀前 $z$ 大的 $f$ 的和。
然后枚举 $k$ 即可得出答案。
参考实现（代码中用 $a, b$ 表示的上述的 $e, f$ ）：
```cpp
#include <cstdio>
#include <algorithm>
#include <queue>
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
struct {
inline operator int () { int x; return scanf("%d", &x), x; }
template<class T> inline void operator () (T &x) { x = *this; }
template<class T, class ...A> inline void operator () (T &x, A &...a)
{ x = *this; this -> operator ()(a...); }
} read;
const int maxn = 100005;
struct obj {
int a, b;
};
obj ob[maxn];
ll lget[maxn], rget[maxn];
int main() {
int x = read, y = read, z = read;
int n = x + y + z;
ll ans = 0;
for(int i = 1; i <= n; i ++) {
int v = read;
ans += v;
ob[i].a = read - v;
ob[i].b = read - v;
}
std::sort(ob + 1, ob + n + 1, [](obj x, obj y) {
return x.a - x.b > y.a - y.b;
});
std::priority_queue<int, std::vector<int>, std::greater<int> > biggest;
for(int i = 1; i <= n; i ++) {
lget[i] = lget[i - 1] + ob[i].a;
biggest.push(ob[i].a);
if(int(biggest.size()) > y) {
lget[i] -= biggest.top();
biggest.pop();
}
}
while(!biggest.empty()) biggest.pop();
for(int i = n; i; i --) {
rget[i] = rget[i + 1] + ob[i].b;
biggest.push(ob[i].b);
if(int(biggest.size()) > z) {
rget[i] -= biggest.top();
biggest.pop();
}
}
ll max = - 1000000000000000000;
for(int k = y; k <= n - z; k ++)
max = std::max(max, lget[k] + rget[k + 1]);
printf("%lld\n", ans + max);
}
```