只有两维的时候,我们显然要按照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个人,然后求和,更新答案。
可以用堆轻松实现。