题解 AT2672 【[AGC018C] Coins】

逃离地球

2020-12-15 00:01:10

Solution

一道挺不错的贪心题,部分分能很大程度地帮助思考。 ### 部分分 1: $X=0$ 对于 $X=0$ 的部分,其实就是给你一堆二元组,让你分组,使得 $\sum y_i+\sum z_i$ 最大。 这是一个挺经典的贪心,考虑两个二元组 $(y_i,z_i)$ 和 $(y_j, z_j)$,若 $y_i+z_j>z_i+y_j$,则有 $y_i-z_i>y_j-z_j$,即 $y-z$ 更大的二元组选 $y$ 一定更优。所以把这些二元组按 $y-z$ 从小到大排序,最大的 $Y$ 个选成 $y$,剩下的选成 $z$ 即可。 ### 部分分 2:$x_i=0$ 这个部分分和上一个的区别,其实就是不需要选所有的二元组,只需要选出 $Y+Z$ 组。 但是上个部分分证明的性质依然成立,即选 $y$ 的二元组的 $y-z$ 一定比选 $z$ 的大。那么如果依旧把这些二元组按 $y-z$ 从小到大排序,一定不会有某个选 $z$ 的二元组在某个选 $y$ 的二元组的右边。 考虑枚举中间点,所有选 $z$ 的都在这个中间点的左边,所有选 $y$ 的都在这个中间点右边。考虑最大化答案,就是在这个中间点左边选出 $z$ 最大的 $Z$ 个二元组,在右边选出 $y$ 最大的 $Y$ 个二元组即可。 计算这玩意是一个曾经见过的 trick,扫一遍,维护一个堆,计算当前选的数中的最小值,和新扫到的数比较大小即可。然后正反都扫一遍就行。~~但我还是想了半天~~ ### 正解: 考虑把 $x_i\ne 0$ 的情况转化为 $x_i=0$ 的情况,只需要把所有二元组的 $y$ 和 $z$ 减去 $x$,然后像上一个部分分一样计算,然后最后在答案里加上 $\sum x$ 即可。