首页 > 试题广场 >

Pokemon

[编程题]Pokemon
  • 热度指数:3988 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛是励志成为世界第一宝可梦大师的宝可梦训练家。现在他遇到了一个强劲的野生宝皮卡丘,野生宝皮卡丘的生命值是HP,攻击力是ACK,牛牛召唤的宝可梦是杰尼龟。杰尼龟的生命值是HP2,攻击力是ACK2,除此之外身为训练家还可以给宝可梦吃药让他满血复活(吃药发生在双方发动攻击之前,并且吃药一方不得在本回合发动攻击)。
牛牛想知道他最少多少回合才能能打败野生宝皮卡丘?
因为皮卡丘会电光一闪,所以皮卡丘总是比杰尼龟先发动攻击。若能成功击败野生皮卡丘则返回最少回合数,否则返回-1。
示例1

输入

8,3,8,1

输出

14

说明

至少需要14回合战胜野生皮卡丘
示例2

输入

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;
    }
}


编辑于 2021-04-10 01:03:39 回复(0)

首先是特判,如果初始时候皮卡丘攻击力大于等于杰尼龟的生命值,那么杰尼龟一直处于死亡复活的死循环中,直接返回 -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,表示第一次攻击。

然后,这里有几个点需要特判:

  • 第一次攻击之后,如果皮卡丘生命值小于等于 0,说明皮卡丘被杰尼龟反杀,直接返回 1
  • 此外,第一次攻击之后,如果杰尼龟剩余生命值小于等于皮卡丘攻击力,那么杰尼龟同样处于死亡复活的死循环中,直接返回 -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;
}
发表于 2020-07-04 17:37:53 回复(0)