Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

08/7
12:32
贪心

[bzoj 2802] [Poi2012]Warehouse Store

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 有一家专卖一种商品的店,考虑连续的n天。
第i天上午会进货Ai件商品,中午的时候会有顾客需要购买Bi件商品,可以选择满足顾客的要求,或是无视掉他。
如果要满足顾客的需求,就必须要有足够的库存。问最多能够满足多少个顾客的需求。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个正整数n (n<=250,000)。
第二行n个整数A1,A2,...An (0<=Ai<=10^9)。
第三行n个整数B1,B2,...Bn (0<=Bi<=10^9)。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

第一行一个正整数k,表示最多能满足k个顾客的需求。
第二行k个依次递增的正整数X1,X2,...,Xk,表示在第X1,X2,...,Xk天分别满足顾客的需求。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

6
2 2 1 2 1 0
1 2 2 3 4 4

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3
1 2 4

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

贪心,每次能卖则卖,否则和当前已经卖的人中去最大的一个和他比大小,用堆来维护,应该是一道双倍经验题但我忘了...

c++:

pascal:

 

[bzoj 2802] [Poi2012]Warehouse Store