USACO 2012 Feb Cow Coupons

題目：

給定 N 隻牛的原價及特價，必須使用一張優惠券才能以特價購買牛，

現在你有 K 張優惠券，以及 M 元，請輸出最多可以買到多少隻牛。

(N <= 50000)



解法：

感覺滿巧妙的，筆記一下，

以下解法為官方解答。

很明顯的，如果從特價最低的牛開始使用優惠券，並不能保證能夠買到最多的牛，

所以在計算的過程中，透過動態修改來保持當前的最佳解，於是由 Greedy 來思考，

設當前某一隻牛的原價為 Pi 、特價為 Ci ，

若 Ci + (Pj - Cj) < Pk ，

其中 Ci 為尚未購買的牛群中特價最低的一隻牛，

Pj - Cj 表示使用優惠券購買的牛群中以特價換回原價所付出的最小代價，

而 Pk 代表尚未購買的牛群中，原價最低的一隻牛，

上式若成立，表示當前以「特價」購進 牛i 是最好的選擇，

若不成立，表示當前以「原價」購進 牛k 是最好的選擇，

由於 Ci 、 Pj - Cj 、Pk 都是當前最小值，

故當購買金額超過 M ，即可結束，此時的購買數量即為最大值。