2519. Going Once, Going Twice, Gone!

单点时限: 2.0 sec

内存限制: 256 MB

The cows’ slimming diet has left Farmer John with extra hay so he has decided to hold an auction to reduce his inventory. He has N (1 <= N <= 1,000) identical lots (each of about 100 bales) of hay; his potential customers comprise M (1 <= M <= 1,000) other farmers

in the area.

Each farmer i tells Farmer John how much he is willing to pay P_i (1 <= P_i <= 1,000,000) for a lot of hay. Each of the farmers wishes to purchase a single lot of hay.

To make sure the other farmers do not get jealous of each other, Farmer John decides that he must sell the lots of hay at a fixed price to each customer who is willing to pay at least that price; the rest will decline the purchase.

Help Farmer John determine the smallest price he should set on a lot of hay to maximize the amount of money he makes.


  • Line 1: Two space-separated integers: N and M

  • Lines 2..M+1: Line i+1 contains a single integer: P_i


  • Line 1: Two space-separated integers: the smallest price that Farmer

John should choose to maximize his revenue and the amount of

money he takes in.


5 4
Farmer John has 5 lots of hay. 4 farmers wish to purchase hay; they
will pay 2, 8, 10, and 7, respectively, for a lot of hay.
7 21
Farmer John should set the price at 7 so that 3 of the farmers will
be willing to pay for a lot of hay, and he will earn 21.

14 人解决,37 人已尝试。

14 份提交通过,共有 75 份提交。

6.9 EMB 奖励。

创建: 11 年,7 月前.

修改: 3 年,2 月前.

最后提交: 7 月,3 周前.

来源: USACO NOV 2008