[noip][复古] NOIP 2007 普及组 守望者的逃离 再叙

Summary：
如果你很着急，找到一种真正正确的不超时的算法，一句话：
枚举休息的时间，剩下的话魔法贪心用完，然后走路，记录更新状态即可。

NOIP普及组一直很简单，不会有某一道题因为什么原因停留在时间的岸边。可是就有那么一道题，在流光里，在长河投 下的点点斑驳中留下。那道题，最有传奇色彩。

如果你还在翻箱倒柜的寻抓哦拿到题，不用那么费劲了，是的他就是 守望者的逃离。

• 悬疑 1： 初看，这道题就是传说中的魔兽的背景，而CCF的那班大叔们真的会对魔兽战役剧情如此了解么？我想大案自 然是否定的。这道题目曾经在百度贴吧了出现过，是的，比赛前。
• 悬疑 2：再看，OOJ上曾经有过那么一到通过人数为1的守望者的逃离。过题的即是“出题”的潘帕斯雄鹰神牛，于是不明 真相的群众么开始怀疑测试数据是错的。神牛抖出了一个测试数据，大家全挂的那个，是对的，此后便不再有问者了。 - 看不懂我在说什么？不知道什么是OOJ？ 那就说明，你还太年轻。
• 悬疑 3：做不来了，外事不决问Google，搜索NOIP2007 普及组 守望者的逃离解题报告，无非以下：

1. 动规 - 那啥就不解释了，严格正确，严格超时。
2. 贪心 - 那个，鹰牛证明过他是不严格正确的，反例很容易举，自己找吧。
3. 动规改进的贪心，官方解法，官方错误，标准的测试数据全过，但是过不了OOJ，具体的反例很难举，算了。

• 于是 悬疑 3 没有正确解题报告的题目。

如是乎看来，若要评选最玄妙的题目，非他莫属啊。

今宵重做此题，突灵感顿发，蓦然回首，那人却在，枚举算法处。

没错，枚举。

我们首先来看一下


定理 1 : 当守望者有魔法时，应该尽早使用闪烁。

证明 :
# 我真得不觉得这个需要证明，但是为了严谨一点，证明好了。

首先思考一下 闪烁的无时效性（无后效性）：

         引理 1 : 对于一次闪烁，当有魔法师，与使用的时间无关。

         引理 1 显然是正确的，那么我们尽早使用闪烁便可以保证闪烁的次数最大，这样便保证了在闪烁时间内走出的距离最大，于是 定理 1 是正确的。



引理 2 : 对于回复魔法，与使用的时间无关。

  由 引理 2 我们可得 ： 若共回复m次魔法，那么可以把他放在开始进行（想象以下wd淡定的在那里回复魔法，看着岛慢慢沉没，然后快速的连放几十个闪烁，就已经离开了荒岛。——WD别扭受的本质啊）

于是 我们可以枚举 回复魔法的时间 rest，然后可以走出的时间为

定理 3 ： 对于魔法为mana，剩余时间为t的状态，最远可以走：

nowdis = min{mana div 10,t} * 60 + 17 * max{0,t-mana div 10}

有 定理1 可以 解释 min{mana div 10,t}*60 这一项（有魔法尽早使用）

后面没魔法了，只有走路。

这样我们以O(1)的时间复杂度计算出了nowdis，而可以用O(t)复杂度枚举（二分好像也可以，但真没必要）rest。

所以我们便敲定了这道题。

童鞋们，记住枚举吧。