【贪心】【堆】AtCoder Grand Contest 018 C - Coins-LMLPHP

只有两维的时候,我们显然要按照Ai-Bi排序,然后贪心选取。

现在,也将人按照Ai-Bi从小到大排序,一定存在一个整数K,左侧的K个人中,一定有Y个人取银币,K-Y个人取铜币;

右侧的X+Y+Z-K个人中,一定有X人取金币,Y+Z-K个人取铜币。

现在,简化一下,我们把每个人的金币数和银币数减去其铜币数,然后默认取上所有人的铜币,这样不影响最终答案。

于是我们依次枚举K,计算前K个人中,银币数之和最大的Y个人,后X+Y+Z-K个人中,金币数之和最大的X个人,然后求和,更新答案。

可以用堆轻松实现。

05-27 20:12