题目出自 USACO 2012 February Contest, Gold Division

题目链接：http://www.usaco.org/index.php?page=viewproblem2&cpid=118

题意

牛市上有 \(N\) 头牛。第 \(i\) 头牛的价格是 \(P_i\) 元。FJ 拿 \(M\) 元钱来买牛。FJ 有 \(K\) 张优惠券，用优惠券买第 \(i\) 头牛的价格是 \(C_i\) 元。一张优惠券只能用一次。FJ 最多能买多少头牛？

限制

• \(1\le N \le 50000\)
• \(1 \le M \le 10^{14}\)
• \(1 \le P_i \le 10^9\)
• \(1 \le C_i \le P_i\)
• \(1 \le K \le N\)
• \(M, P_i, C_i\) 是整数。

贪心算法

我们证明下述策略将导致一个全局最优解。

每次付出最少的钱多买一头牛。

换言之，“每次增量最少”将导致全局最优解。具体地，前 \(K\) 头牛，买 \(C_i\) 前 \(K\) 小的牛。以后每次买 \(\min(C_i + \Delta_K , P_i)\) 最小的牛；\(\Delta_K\) 表示已买的牛中第 \(K\) 大的 \(P_i\) 和 \(C_i\) 的差值。

设当前已买的牛的集合是 \(S\)。我们证明：

\(S\) 总是某个最优解的子集。

容易证明，\(C_i\) 前 \(K\) 小的 \(K\) 头牛是某个最优解的子集。

设 \(|S| \ge K\)，\(S\) 是最优解 \(T\) 的子集，牛 \(i\) 是剩下的牛里让 \(\min(C_j + \Delta_K, P_j)\) 取最小值的牛，且牛 \(i\) 不在 \(T\) 里。设 \(S\) 里 \(P_j\) 和 \(C_j\) 差值第 \(K\) 大的牛是牛 \(k\)。我们证明：

存在牛 \(j\in T\setminus S\) 满足：把牛 \(j\) 换成牛 \(i\)，花的钱不会更多。

情况一：\(P_i \le C_i + \Delta_K\)。此时对于每个 \(j \in T \setminus S\) 都有 \(P_i \le P_j\) 且 \(P_i \le C_j + \Delta_K\)。

• 若 \(T \setminus S\) 里有未用优惠券买的牛，任取一个这样的牛和牛 \(i\) 交换。
• 若 \(T \setminus S\) 里的牛都用优惠券了，则 \(S\) 里的牛 \(k\) 一定没用优惠券；从 \(T\setminus S\) 里任取一头牛 \(j\)，不买 \(j\)，用优惠券买牛 \(k\)，原价买牛 \(i\)。由 \(P_i \le C_j + \Delta_K\) 可知这样买花的钱不会更多。

情况二：\(P_i > C_i + \Delta_K\)。此时对于每个 \(j \in T \setminus S\) 都有 \(C_i + \Delta_K \le C_j + \Delta_K\)，即 \(C_i \le C_j\)；和 \(C_i + \Delta_K \le P_j\)。

• 若 \(T \setminus S\) 里有用优惠券买的牛，任取一头这样的牛和牛 \(i\) 交换。
• 若 \(T \setminus S\) 里没有用优惠券买的牛，则 \(S\) 里的牛 \(k\) 一定用了优惠券。从 \(T \setminus S\) 里任取一头牛 \(j\)，不买 \(j\)，用优惠券买牛 \(i\)，原价买牛 \(k\)。由 \(C_i + \Delta_K \le P_j\) 可知这样买花的钱不会更多。