Cow Coupons要点

· · 题解

FJ准备买一些新奶牛，市场上有N头奶牛(1<=N<=50000)，第i头奶牛价格为Pi(1<=Pi<=10^9)。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci(1<=Ci<=Pi)，每

头奶牛只能使用一次优惠券。FJ想知道花不超过M(1<=M<=10^14)的钱最多可以买多少奶牛？

重点关于 怎样区分是否用原价买 分为两种

将目前价格最下和优惠价格最下

的差值，与目前已经买的优惠最小的作对比

如果价格最低的减去优惠价格最低比优惠最小的值大 则证明用买原价的更优 否则 买优惠的更优

delta.top() > x1.first-x2.first

如上，也可以想成，买x2.first时，会亏损delta.top（）；再将更便宜的入队。