题解 | #Pokemon#_牛客博客

思路

题目分析

题目给出我们皮卡丘和杰尼龟两方，都有HP值和ACK攻击值
每个回合允许双方攻击对方一次，其中杰尼龟可以选择将此回合的一次攻击换成回复满血量
每个回合必须皮卡丘先攻击
求最终杰尼龟是否能打败皮卡丘，并返回打败皮卡丘所用的回合数

最容易想到的方法一就是暴力推演整个攻击过程，用一个循环模拟整个攻击场景，不断记录血量变化并检验最终的结果和回合数
优化方案方法二是数学推理，通过双方的HP值和ACK值来推理皮卡丘死亡最终需要几个回合，并计算好杰尼龟需要恢复多少次，将这两组数据加和就是最终的回合数。

方法一：暴力推演

图片说明

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param HP long长整型 HP
     * @param ACK long长整型 ACK
     * @param HP2 long长整型 HP2
     * @param ACK2 long长整型 ACK2
     * @return long长整型
     */
    long long Pokemonfight(long long HP, long long ACK, long long HP2, long long ACK2) {
        // write code here
        // 杰尼龟打不过皮卡丘有两种情况
        if(ACK >= HP2 || (ACK2 < HP && ACK*2 >= HP2)) return -1;

        // 杰尼龟一次就打死皮卡丘
        if(ACK2 >= HP) return 1;

        // 杰尼龟all回合才打死皮卡丘
        long long all = 0;
        long long tempHP2 = HP2;
        while(HP > 0){
            all++;
            if(tempHP2 > ACK) {        // 不需要加血
                tempHP2 -= ACK;
                HP -= ACK2;
            }
            else {                     // 需要加血
                tempHP2 = HP2 - ACK;
            }
        }
        return all;
    }
};

复杂度分析

时间复杂度： $O(N)$ ，一重循环，与皮卡丘的HP值有关
空间复杂度： $O(1)$ ，没有借助额外空间

方法二：数学推理

我们令a表示皮卡丘遭受a次攻击最后死亡，所以a就是ceil(HP/ACK2)次，这里采用上取整的方式，因为对于小数点不满一次攻击的情况，我们也需要计入一次。
我们令b表示杰尼龟遭受b次攻击后达到斩杀线（斩杀线：下一次受到攻击就死亡的血量线），就是b次攻击后，杰尼龟下一次再遭受皮卡丘的攻击就会死亡，因此b 就是 ceil(HP2/ACK)-1。其中ceil(HP2/ACK)是让杰尼龟必死的次数，减1才是让杰尼龟达到斩杀线的次数。
最后我们计算blood表示杰尼龟在回合中总共几次选择恢复血量。
- 由于第a打到皮卡丘的时候，皮卡丘就挂了，这一次不用考虑加血，在前a-1次打到皮卡丘的过程中我们要考虑给杰尼龟加血。
- 并且我们不能等到杰尼龟受到了b次攻击到了斩杀线的时候才准备下一次加血（因为下一次是皮卡丘先攻击，杰尼龟就挂掉了），所以杰尼龟必须在b-1次受到伤害的时候，下一次加血才正好
- 因此ceil((a-1)/(b-1))表示杰尼龟需要加血的次数，首先(a-1)/(b-1)必须向上取整，这样才保证满足我们前两点加上血的需求，但是这个次数仍然不准确。因为我们总是在杰尼龟未达到斩杀线的回合的下一回合（也就是下一次受伤就会达到斩杀线）加血，在最后一次与皮卡丘的对战中，我们不需要加血最后一次也可以杀掉皮卡丘了，就不存在下一轮皮卡丘会由于可以率先攻击而杀掉杰尼龟的情况，最后一次加血是没有必要的。
- 因此加血的次数最终为ceil((a-1)/(b-1))-1
所有*1.0是为了避免整数相除直接取整的情况，转换成浮点数可以帮助我们实现上取整。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param HP long长整型 HP
     * @param ACK long长整型 ACK
     * @param HP2 long长整型 HP2
     * @param ACK2 long长整型 ACK2
     * @return long长整型
     */
    long long Pokemonfight(long long HP, long long ACK, long long HP2, long long ACK2) {
        // write code here
        // 杰尼龟打不过皮卡丘的两个情况
        if(ACK >= HP2 || (ACK2 < HP && ACK*2 >= HP2)) return -1;

        // 杰尼龟打得过皮卡丘，一回合结束战斗
        if(ACK2 >= HP) return 1;

        // 杰尼龟皮卡丘多回合战斗，最终杰尼龟战胜
        long long a = ceil(HP*1.0/ACK2);            //皮卡丘总计被攻击a次死掉，战斗结束
        long long b = ceil(HP2*1.0/ACK)-1;          //杰尼龟被攻击m次会达到斩杀线
        long long blood = ceil((a-1)*1.0/(b-1))-1;  //每经过(m-1)次互相攻击杰尼龟要回复一次，一共需要回复的次数
        return a+blood;
    }
};

复杂度分析

时间复杂度： $O(1)$ ，没有循环的时间代价。
空间复杂度： $O(1)$ ，只使用了有限的变量。