返回信息流华为第三题，怎么处理等不等魔法？
题目：
某游戏中，玩家的任务是杀死终极BOSS。BOSS和玩家战斗方式为回合制，玩家先发动进攻。BOSS的攻击方式为：普通攻击和暴击，每4回合普通攻击的下一回合攻击为暴击。BOSS的普通攻击力为10点HP，暴击时的攻击力为普通攻击的3倍。玩家的攻击方式为：普通攻击和魔法攻击。玩家的普通攻击为17点HP，魔法攻击为60点HP。使用魔法攻击时需要消耗10点魔法值，魔法值来源有两种：初始魔法量和回合内选择魔法恢复，魔法恢复速度为4点/回合，魔法恢复回合内无法发动攻击。每轮回合开始时，玩家可以选择：普通攻击、魔法攻击或恢复魔法三种行动方式之一。现已知玩家的HP和初始魔法量，BOSS的HP，编写程序，求玩家战胜BOSS的最小回合数。
运行时间限制: 1 Sec
内存限制: 100 MByte
输入:
输入三个整数HP1(0<HP1<=10000),MP(0<MP<=1000),HP2(0<HP2<=10000),分别为玩家的HP、玩家的初始魔法量和BOSS的HP。
输出:
若玩家可以战胜BOSS输出战胜BOSS的最小回合数,否则输出-1。
样例输入:
100 20 100
样例输出:
2
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89641同步于 2016/4/13
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
华为第三题，怎么处理等不等魔法？
lee123
2016/4/13镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
游戏一共有N回合。
我们枚举有多少回合玩家使用普通攻击。再由此推算出有多少回合使用膜法攻击。再根据所需要的膜法值估算总共需要多少个回合恢复膜法（a.k.a 提升自己的姿势水平）。
时间复杂度为O(n)。所以就是大概(HP2/17)这个数量级。随便搞一下就好了嘛。
没有提交过，思路是这样的，也许有问题。
* 空魔法时，7个回合可以恢复20点魔法并魔法攻击两次，输出 120
* 7个回合纯物理输出119
所以BOSS的生命值足够多的时候，一直选择魔法输出效率是最高的
如果初始魔法有剩余，那么可以更早完成120的输出，而且7个回合总是一个循环
极限输出，我们分三个阶段：（每个阶段都要注意BOSS挂没有）
1 初始魔法攻击：消耗初始的魔法值进攻，之后会剩余部分魔法值
2 BOSS的剩余血量如果大于120，那么按照上面的推断，进行恢复、魔法输出
3 现在BOSS的血量降到了120或以下，比较魔法输出和物理输出的效率：
初始剩余魔法的影响如下：
0 1 2 3 4 5 6 7
================================
0 4 8 12 (2) 6 10 (0)
1 5 9 13 (3) 7 11 (1)
2 6 10 (0) 4 8 12 (2)
3 7 11 (1) 5 9 13 (3)
4 8 12 (2) 6 10 (0) 4
5 9 13 (3) 7 11 (1) 5
6 10 (0) 4 8 12 (2) 6
7 11 (1) 5 9 13 (3) 7
8 12 (2) 6 10 (0) 4 8
9 13 (3) 7 11 (1) 5 9
我们可以得到魔法输出的回合数
restHP <= 60:
0,1:4
2,3,4,5:3
6,7,8,9:2
60 < restHP <= 120
0,1,2,3:7
4,5,6,7:6
8,9:5
再比较restHP需要的物理输出回合得到最小的回合数。
计算这三个阶段的值求和可以得到打死BOSS需要的回合数，如果BOSS提前死了后面的阶段就不用算了。
BOSS的输出模式则是固定的，可以算出玩家生存的回合数，比较一下就能得出玩家能不能打死BOSS。
如果逻辑没问题的话，这么做复杂度是O（1）？
【 在 lee123 的大作中提到: 】
: 华为第三题，怎么处理等不等魔法？
: 题目：
: 某游戏中，玩家的任务是杀死终极BOSS。BOSS和玩家战斗方式为回合制，玩家先发动进攻。BOSS的攻击方式为：普通攻击和暴击，每4回合普通攻击的下一回合攻击为暴击。BOSS的普通攻击力为10点HP，暴击时的攻击力为普通攻击的3倍。玩家的攻击方式为：普通攻击和魔法攻击。玩家的普通攻击为17点HP，魔法攻击为60点HP。使用魔法攻击时需要消耗10点魔法值，魔法值来源有两种：初始魔法量和回合内选择魔法恢复，魔法恢复速度为4点/回合，魔法恢复回合内无法发动攻击。每轮回合开始时，玩家可以选择：普通攻击、魔法攻击或恢复魔法三种行动方式之一。现已知玩家的HP和初始魔法量，BOSS的HP，编写程序，求玩家战胜BOSS的最小回合数。
: ...................