题解 | #Pokemon#

思路：

题目的主要信息：

• 皮卡丘的生命和攻击力分别为HP与ACK，杰尼龟的生命与攻击力分别为HP2与ACK2，默认攻击一次对方生命值减去攻击力的数值
• 杰尼龟可以选择恢复全额生命到HP2，但是该轮不能攻击
• 每个回合皮卡丘优先攻击，如果杰尼龟处于不断复活的循环中则认定不能打败皮卡丘，返回-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;
        if(ACK2 >= HP) //不用吃药硬抗一次，第一轮获胜
            return 1;
        long long res = 0;
        long long temp = HP2; //暂存现在血量
        while(HP > 0){
            res++;
            if(temp > ACK){ //不用吃药
                temp -= ACK;
                HP -= ACK2;
            }
            else
                temp = HP2 - ACK;//吃药挨打
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，n为皮卡丘血量HP
• 空间复杂度：，无额外空间

方法二：数学规律
具体做法：
仔细观察方法一中模拟的最终战况图：

我们可以发现除了第一轮其他轮都是循环，我们可以用找到每个循环的回合数，每个回合会因回复少攻击一次，因此每个循环的有效攻击为，利用这两个数据我们就可以知道打败皮卡丘的接近数据，为什么是接近，为开头有第一回合，结尾需要有考虑残局要不要回复以及不满一个循环等问题。

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;
        if(ACK2 >= HP) //不用吃药硬抗一次，第一轮获胜
            return 1;
        long long res = 1;
        HP -= ACK2; //除去第一轮
        long long countOfCycle = (HP2 - 1) / ACK; //找到循环的回合数
        long long ackOfCycle = (countOfCycle - 1) * ACK2;    // 每个循环可以贡献的攻击力 
        long long basicCount = HP / ackOfCycle;//一共需要几轮
        res += basicCount * countOfCycle; 
        long long restHP = HP % ackOfCycle;//这些攻击之后，HP 还剩下多少
        if (restHP == 0) //最后一次不需要复活，直接拿下
            res--;
        else
            res += restHP / ACK2 + (restHP % ACK2 == 0 ? 0 : 1);// 如果还有血，不需要在进行完整的循环 
        return res;
    }
};

复杂度分析：

• 时间复杂度：，没有循环，常数时间
• 空间复杂度：，常数的空间变量