很板的题。考虑反悔贪心，当可以满足顾客的需求时就满足；如果满足不了，且这个顾客的需求比之前那个花费最大的顾客要小，那就不要满足之前那个顾客，满足当前的顾客。可以证明，这一定是最优的。
那么考虑如何维护这一操作。可以维护一个 priority_queue，且是大根堆。每次查队首元素是否满足上述的特征。
因为要记录满足的是那几个顾客，可以用一个 vis 数组标记。
1 个赞
很板的题。考虑反悔贪心，当可以满足顾客的需求时就满足；如果满足不了，且这个顾客的需求比之前那个花费最大的顾客要小，那就不要满足之前那个顾客，满足当前的顾客。可以证明，这一定是最优的。
那么考虑如何维护这一操作。可以维护一个 priority_queue，且是大根堆。每次查队首元素是否满足上述的特征。
因为要记录满足的是那几个顾客，可以用一个 vis 数组标记。