现在有 \(X+Y+Z\) 个人，第 \(i\) 个人有三个权值 \(a_i,b_i,c_i\)，现在要求依次选出 \(X\) 个人，\(Y\) 个人和 \(Z\) 个人（一个人只能选依次），使得这 \(X\) 个人的 \(a\) 权值，\(Y\) 个人的 \(b\) 权值，\(Z\) 个人的 \(c\) 权值之和最大。
\(X,Y,Z\le 10^5\)。
技巧：排序证明贪心的正确性
一道很有启发意义的贪心题。
考虑只有两种权值 \(a,b\) 的时候我们怎么做，我们会先假设所有人都选 \(b\)，然后把所有人按 \(a_i-b_i\) 从大到小排序，选前 \(X\) 个人从 \(b\) 变成 \(a\)。
这个贪心过程的正确性显然，但却不是很好严谨地证明。但是我们考虑这样一种表述方式：
“将所有人按照 \(a_i-b_i\) 从大到小排序，那么所有选择 \(a\) 的人一定排在所有选择 \(b\) 的人左边。”
这个的证明非常简单明了：如果有左 \(b\) 右 \(a\) 的对，把他们交换，显然很优！
而这个证明的简单明了，意味着它的做法可以放到这道题上面。
具体地，我们仍然把所有人按 \(a_i-b_i\) 从大到小排序，那么所有选择 \(a\) 的人依然一定排在所有选择 \(b\) 的人左边，尽管不是所有人都选了 \(a\) 或 \(b\)。
于是一定存在一个分界点 \(k\)，在 \(k\) 左边的所有人选的都是 \(a\) 或 \(c\)，在 \(k\) 右边的所有人选的都是 \(a\) 或 \(b\)。
两边分别拿个对顶堆维护即可。时间复杂度 \(O(n\log n)\)。
标签：所有人,个人,Coins,从大到,权值,AGC018C,排序,贪心 From： https://www.cnblogs.com/Charlie-Vinnie/p/17557750.html