[AGC018C] Coins 题解

题目链接：[AGC018C] Coins

题意：

有 \(x+y+z\) 个人，第 \(i\) 个人有 \(A_i\) 个金币，\(B_i\) 个银币，\(C_i\) 个铜币。

要选出 \(x\) 个人获得其金币，选出 \(y\) 个人获得其银币，选出 \(z\) 个人获得其铜币。在不重复选某个人的情况下，最大化获得的币的总数。

数据范围：

\(1\le x+y+z\le 10 ^ 5,1 \le A_i,B_i,C_i \le 10^9\) 。

做法和 P5470 [NOI2019] 序列 类似，经典套路了。

我们可以先凑满 \(x,y,z\) 人，然后开始反悔贪心。

1. 将一个 \(x\) 放到 \(y\) 去，再从 \(y\) 中拿一个到 \(x\) 。
2. 将一个 \(x\) 放到 \(z\) 去，再从 \(z\) 中拿一个到 \(x\) 。
3. 将一个 \(y\) 放到 \(z\) 去，再从 \(z\) 中拿一个到 \(y\) 。
4. 将一个 \(x\) 放到 \(y\) 去，再从 \(y\) 中拿一个到 \(z\) ，最后从 \(z\) 中拿一个到 \(x\) 。
5. 将一个 \(x\) 放到 \(z\) 去，再从 \(z\) 中拿一个到 \(y\) ，最后从 \(y\) 中拿一个到 \(x\) 。

那么我们维护所有转移产生的贡献即可，也就是弄 \(6\) 个堆。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码详见参考文献1，实现类似 P5470 。

---

参考文献：

[1] https://www.luogu.com.cn/article/3wnlp2ld