综合题： AGC018C Coins
大致可以分为两种类型， 即要求全选或者有的可以不选。
第一类: 要求全选
问题简述： 给定\(x + y\)个物品， 每个物品有\(a_i\), \(b_i\)两种属性， 要求取出\(x\)个\(a\)属性， \(y\)个\(b\)属性， 要求属性和最大
解决方案： 先假设每个物品都取\(a\)属性，那么要把一个物品变成\(b\)属性的代价为\(b_i - a_i\), 用大根堆维护，取最大的\(y\)个即可.
第二类： 有的可以不选
问题简述： 给定\(n\)个物品， 每个物品有\(a_i\)和\(b_i\)两种属性， 要求取出\(x\)个\(a\)属性， \(y\)个\(b\)属性， 要求属性和最大。（保证\(x + y < n\)）
解决方案： 因为有的物品可以不选，所以第一类的解决方案明显不可以。 我们假设\(c_i = b_i - a_i\)
考虑什么时候\(i\)取\(a\) , \(j\) 取\(b\)时比\(i\)取\(b\) , \(j\) 取\(a\)时优
\[a_i + b_j > b_i + a_j \]\[a_i - b_i > b_i - b_j \]\[c_i > c_j \]所以对于任意取\(a\)的\(i\)和任意取\(b\)的\(j\)都有\(c_i > b_j\). (否则一定不是最优，调整法可证。)
因此我们可以按\(c_i\)从小到大排序后。 枚举断点，断点后边取\(x\)个最大的\(a_i\), 前面取\(y\)个最大的\(b_i\), 这个东西可以用优先队列预处理.
综上时间复杂度为\(O(n\log_{2}n)\)
标签：总结,要求,解决方案,不选,反悔,物品,贪心,断点,属性 From： https://www.cnblogs.com/absolutey/p/16941065.html