HDU

题目大意

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有 (n) 种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

样例

样例输入 1

10
1 2 3 2 1 1 2 3 2 1
50

样例输出 1

样例 1 说明

有 10 种菜，结果自己算吧

样例输入2

1
50
5

样例输出2

-45

样例 2 说明

只有一种菜，价格为 (50)，卡上余额 (5) 元，此时买这个菜，剩余 (-45)。

分析

按照惯例，特殊处理一部分数据：
- 当初始余额 (money) 小于 (5) 的时候，什么都不能买，直接输出即可
- 当所有菜价总和 (sum+5) 不大于初始余额时，表示所有菜都能买，直接输出 (money-sum)
对于一般情况来说，假设手里只有 (5) 块，买价格最高的菜才是最优解
如果余额大于 (5) 块，我们可以把最贵的菜放到最后买，用前面的 (n-1) 个菜去凑不大于 (money-5) 的最大值，用剩下的钱买最贵的菜即可。为什么这样时对的呢？
- 如果拿出最贵的菜之后，剩下的菜可以恰好凑成 (money-5)，显然时最优的
- 如果拿出最贵的之后，剩下的不能凑成恰好等于 (money-5)，这样做还是最优的吗？当然是的，证明如下：
  - 假设不是最优的，那么会有一种方案将最后一个菜加入到 (money-5) 的组合中，设组合为 ({p_1, p_2, ..., p_n})，它们的和为 (m(m le money-5))，而选择最后买的菜价格为 (p_k)，且 (p_n > p_k)，此时最终的余额为 (t = money - m - p_k)
  - 那么我们可以转换一下，既然选择的组合可以加入 (p_n)，那么小于 (p_n) 的菜来替换 (p_n) 的时候，都能保证 (m <= money-5)
  - 我们将 (p_n) 与 (p_k) 对换一下，则选菜的组合的总和变成了 (m' = m - (p_n-p_k))，最终余额为 (t' = money-m'-p_n=money-m+(p_n-p_k)-p_k=t)
  - 也就是说两种的答案是一样的，换句话说，我们把最贵的留在最后买，最终的余额不会大于其他的方案

代码

代码就不写了，没有什么可写的