牛牛是励志成为世界第一宝可梦大师的宝可梦训练家。现在他遇到了一个强劲的野生宝皮卡丘,野生宝皮卡丘的生命值是HP,攻击力是ACK,牛牛召唤的宝可梦是杰尼龟。杰尼龟的生命值是HP2,攻击力是ACK2,除此之外身为训练家还可以给宝可梦吃药让他满血复活(吃药发生在双方发动攻击之前,并且吃药一方不得在本回合发动攻击)。
牛牛想知道他最少多少回合才能能打败野生宝皮卡丘?
因为皮卡丘会电光一闪,所以皮卡丘总是比杰尼龟先发动攻击。若能成功击败野生皮卡丘则返回最少回合数,否则返回-1。
8,3,8,1
14
至少需要14回合战胜野生皮卡丘
1,1,1,1
-1
皮卡丘先出招就直接打死了杰尼龟,所以无法获胜
import java.util.*; public class Solution { public long Pokemonfight (long HP, long ACK, long HP2, long ACK2) { if(ACK >= HP2){ //第一回合,先被打,一下被K.O.,打不过 return -1; } if(ACK2 >= HP){ //苟过第一下就能立马反杀,能打过,一局结束 return 1; } if(HP2 - ACK <= ACK){ //回血后没机会打,一直只能回血,打不过 return -1; } long n = HP%ACK2==0? HP/ACK2 : HP/ACK2+1; //皮卡丘被攻击总次数 long m = HP2%ACK==0? HP2/ACK-1 : HP2/ACK; //第一次回血前的攻击次数 long drug = (n-1)%(m-1)==0?(n-1)/(m-1) - 1 : (n-1)/(m-1); //回血次数 return n + drug; } }
首先是特判,如果初始时候皮卡丘攻击力大于等于杰尼龟的生命值,那么杰尼龟一直处于死亡复活的死循环中,直接返回 -1
接下来,以例子(15 3 10 2)说明:
杰尼龟 皮卡丘 10 -> 7 15 -> 13 7 -> 4 13 -> 11 4 -> 1 11 -> 9 1 -> 10 -> 7 9 7 -> 4 9 -> 7 4 -> 1 7 -> 5 1 -> 10 -> 7 5 7 -> 4 5 -> 3 4 -> 1 3 -> 1 1 -> 10 -> 7 1 7 -> 4 1 -> GG
没有直接返回,说明杰尼龟抗住了第一次攻击,并且发起了一次反击,皮卡丘的生命值降低,变为 HP = HP - ACK2
。
所以,可以声明 result
记录一共需要的回合数,同时初始化 result
为 1,表示第一次攻击。
然后,这里有几个点需要特判:
再来看除第一次攻击之外的其余的部分,容易得到这部分存在循环(也就是 1 -> 7 -> 4 -> 1 -> ···):
countOfCycle = (HP2 - 1) / ACK
ackOfCycle = (countOfCycle - 1) * ACK2
这样就可以计算出“至少”需要几轮才可以打败皮卡丘,即 basicCount = HP / ackOfCycle
知道了“至少”需要几轮之后,可以将这部分直接接到 result
上,即 result += basicCount * countOfCycle
需要注意的是,计算 basicCount
时默认是向下取整,那么还要判断皮卡丘是否还有血,即 leftHP = HP % ackOfCycle
是否为 0
leftHP
为 0,说明正好结束掉皮卡丘,但是也增加了一次复活,需要减去 leftHP
不为 0,说明皮卡丘还有血,需要计算出还需要几个回合,也就是 result += leftHP / ACK2 + (leftHP % ACK2 == 0 ? 0 : 1)
public long pokemonFight(long HP, long ACK, long HP2, long ACK2) { /* 杰尼龟处于死亡复活的死循环中,不可能发动攻击 */ if (HP2 <= ACK) { return -1; } long result = 1; /* 第一次攻击 */ HP -= ACK2; if (HP <= 0) { /* 皮卡丘被杰尼龟瞬秒,直接返回 1 */ return result; } else if ((HP2 - ACK) <= ACK) { /* 杰尼龟处于死亡复活的死循环中,直接返回 -1 */ return -1; } /* 几个回合是一个循环 */ long countOfCycle = (HP2 - 1) / ACK; /* 每个循环可以贡献的攻击力 */ long ackOfCycle = (countOfCycle - 1) * ACK2; /* 一共需要几轮 */ long basicCount = HP / ackOfCycle; result += basicCount * countOfCycle; /* 这几轮攻击之后,HP 还剩下多少 */ long leftHP = HP % ackOfCycle; if (leftHP == 0) { /* 如果 leftHP 为 0,说明正好够用,并且最后一次不需要复活 */ result -= 1; } else { /* 如果 leftHP 不为 0,说明还有血,但不需要在进行完整的循环 */ result += leftHP / ACK2 + (leftHP % ACK2 == 0 ? 0 : 1); } return result; }