题解 | #牛牛打怪兽#

一.题目描述
NC564牛牛打怪兽
现在牛牛面前有n只怪兽，第i只怪兽的血量为ai。牛牛可以使用这个组合拳打第X怪兽，同时会打到第2X、2X+1这两个怪兽，每次组合拳会扣打到的怪兽一滴血。一个怪兽血量为0即为死亡，同时组合拳是可以鞭尸的，这意味着即使怪兽死亡，也可以对其使用组合拳。值得注意的是组合拳必须攻击三只怪兽。牛牛想知道它需要使用最少多少次组合拳才能把所有怪兽打死，如果打不死请输出-1。
图片说明
二.算法(模拟)

首先我们要意识到组合拳是一次性可以打三只怪兽，并且打第X怪兽的时候，同时会打到第2X、2X+1这两个怪兽，每次组合拳会扣打到的怪兽一滴血，也就是说只有怪兽的数目是奇数的时候(而且数量大于2)才可以把所有怪兽打死，对于可以打死所有怪兽的情况，我们只需要利用数组进行模拟就行了，下面是完整代码：

class Solution {
public:
    int slove(int n, vector<int>& A) {
        //特判断 无法将所有的怪兽消灭的怪兽数目
        if(n<=2||(n%2==0)){
            return -1;
        }
        //记录需要打的组合数数目
        int ans=0;
        for(int i=n/2-1;i>=0;i--){
            //下标是从0开始的 所以是2*i+1和2*i+2
            int a=max(A[2*i+2],A[2*i+1]);
            //要是怪兽已经死了 直接为0
            A[i]=max(A[i]-a,0);
            ans+=a;
        }
        //这块要注意最后一个怪兽要对其施加A[0]次组合拳
        return ans+A[0];
    }
};

时间复杂度： $O(n)$ 只需要对数组进行一次遍历
空间复杂度： $O(1)$ 不需要额外空间
优缺点：时间复杂度低，代码简单便于实现。
三.算法(利用java实现)
利用java同样可以实现下面是完整代码：

import java.util.*;
public class Solution {
    public int slove (int n, int[] A) {
         //特判断 无法将所有的怪兽消灭的怪兽数目
        if(n<=2||(n%2==0)){
            return -1;
        }
        //记录需要打的组合数数目
        int ans=0;
        for(int i=n/2-1;i>=0;i--){
            //下标是从0开始的 所以是2*i+1和2*i+2
            //利用Math类判断大小
            int a=Math.max(A[2*i+2],A[2*i+1]);
            //要是怪兽已经死了 直接为0
            A[i]=Math.max(A[i]-a,0);
            ans+=a;
        }
        //这块要注意最后一个怪兽要对其施加A[0]次组合拳
        return ans+A[0];
    }
}

时间复杂度： $O(n)$ 只需要对数组的一半进行一次遍历
空间复杂度： $O(1)$ 不需要额外空间来存储数据
优缺点：时间复杂度低，代码简单和c++一样便于实现。