题解 | #Pokemon#_牛客博客

题目描述
牛牛是励志成为世界第一宝可梦大师的宝可梦训练家。现在他遇到了一个强劲的野生宝皮卡丘，野生宝皮卡丘的生命值是HP，攻击力是ACK，牛牛召唤的宝可梦是杰尼龟。杰尼龟的生命值是HP2，攻击力是ACK2，除此之外身为训练家还可以给宝可梦吃药让他满血复活(吃药发生在双方发动攻击之前，并且吃药一方不得在本回合发动攻击)。
牛牛想知道他最少多少回合才能能打败野生宝皮卡丘？
因为皮卡丘会电光一闪，所以皮卡丘总是比杰尼龟先发动攻击。若能成功击败野生皮卡丘则返回最少回合数，否则返回-1。

方法一：暴力解法

求解思路
对于本题求解最少多少次可以击败野生皮卡丘，我们对所有的情况进行模拟枚举即可，即只要牛牛的宝可梦这回合不被打死就继续战斗，要是被打死就喝药，根据上述思路我们便可得到本题的解。

图片说明

解题代码

class Solution {
public:
    long long Pokemonfight(long long HP, long long ACK, long long HP2, long long ACK2) {
        if(ACK>=HP2||(ACK*2>=HP2&&ACK2<HP))
        {
            return -1; // 打不死的情况，返回-1
        }
        if(ACK2>=HP)
        {
            return 1; // 战胜的情况
        }
        long long total = 0;
        long long nowHP = HP2;
        while(HP>0)
        {
            total++; // 回合数
            if(nowHP>ACK) nowHP-=ACK,HP-=ACK2;
            else nowHP=HP2-ACK;
        }
        return total; // 返回最终的结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：优化求解

求解思路
对于本问题，牛牛的宝可梦需要吃药的时候肯定是撑不住的那一回合，所以我们需要计算杰尼龟需要吃多少次药，然后才能战胜野生皮卡丘。我们需要注意杰尼龟可能第一回合打不过皮卡丘，或者杰尼龟可以直接打死皮卡丘，或者杰尼龟在第二回合就被打死的情况。根据上述思路和需要注意的情况，我们即可得到本题的答案。

图片说明

解题代码

class Solution {
public:
    long long Pokemonfight(long long HP, long long ACK, long long HP2, long long ACK2) {
        if(ACK>=HP2||(ACK*2>=HP2&&ACK2<HP))
        {
            return -1; // 打不过，返回-1
        }
        if(ACK2>=HP)
        {
            return 1; // 第一回合击败野生皮卡丘
        }
        long long myans=1; // 提前处理第一回合，因为之后靠喝药剩下的血量都只有HP2-ACK
        HP=max(0ll,HP-ACK2);
        long long times=(HP2-ACK)/ACK; // 不吃血包能攻击的回合数
        if((HP2-ACK)%ACK!=0) times++;
        times--; // 最后一回合需要喝药保命
        long long allack;
        long double x=1;
        if(x*times*ACK2>=1e18)
            allack=1e18;
        else allack=times*ACK2;
        long long fight=HP/allack; // 计算完整吃血回合数
        if(HP!=0&&HP%allack==0)
            myans--; // 更新结果
        long long lef=HP-fight*allack;
        myans+=fight*(times+1);
        myans+=lef/ACK2;
        if(lef%ACK2!=0)
            myans++;
        return myans; // 返回结果
    }
};

复杂度分析
时间复杂度：常数级时间复杂度，因此为 $O(1)$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$