BZOJ 2802 [Poi2012]Warehouse Store

发布于 2017-08-06  190 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2802

题意:考虑连续的 n 天。第 i 天上午会进货\(a_i\) 件商品,中午的时候会有顾客需要购买\(b_i\) 件商品,可以选择满足顾客的要求,或是无视掉他。问最多能够满足多少个顾客的需求。


大概也算是经典题了,贪心的思路是显然的。

能满足就满足,显然是错误的思路,因为可能满足了太贵的顾客使得无法满足后面很多便宜的顾客。

所以让我们可以“后悔”,每次若不可以满足某顾客,则在前面满足了的顾客中选择一个较劣的换掉。

显然换掉最劣的那个是最优的,这个过程可以用一个堆维护。没了。

 


一个非常弱的准退役OIER