[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