题解 | #牛牛打怪兽#

题目：

牛牛面前有n只怪兽，第i只怪兽的血量为A[i]。牛牛刚刚从牛毕哪里学到一套组合拳, 当使用这个组合拳的时候，打第X只怪兽的时候，同时会打到第2X、2X+1这两个怪兽，每次组合拳会扣打到的怪兽一滴血。一个怪兽血量为0即为死亡，同时组合拳是可以鞭尸的，这意味着即使怪兽死亡，也可以对其使用组合拳。 值得注意的是组合拳必须攻击三只怪兽 牛牛想知道它需要使用最少多少次组合拳才能把所有怪兽打死，如果打不死请输出-1。

方法一：贪心

• 因为打第i只怪兽时会同时打到第2i和2i+1只怪兽，则2i+1可以取得的最大值为n，因此n必须为奇数，假设n可以为偶数，则为2的倍数，设n=2i，则打第i只怪兽时，会同时打到第2i和2i+1只怪兽，2i+1会越界，而题目要求组合拳必须攻击三只怪兽，因此n只能取偶数；当n小于3时，也无法展开组合拳，因此都返回-1

• 由得,则i从$(n-1)\mathrm{/}2-1(n-1)/2-1$递减，每次打第i只怪兽，相应打到第2i,2i+1只，对应到数组中就是A[2i+1],A[2i+2],取其中的最大值max，血量较小的那只也会被消耗完，而A[i]会相应减少血量到max(A[i]-max,0),累加max，最后加上A[0]的剩余血量

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个怪兽
     * @param A int整型vector A数组代表每个怪兽的血量
     * @return int整型
     */
    int slove(int n, vector<int>& A) {
        // write code here
        if(n<3||n%2==0)return -1;//偶数或者小于3都无法使用组合拳
        int num=0;
        for(int i=(n-1)/2-1;i>=0;i--){//从中间开始
            int temp=max(A[2*i+1],A[2*i+2]);//取2*i+1和2*+2的最大值，较小的也会消耗到0
            num+=temp;
            A[i]=max(A[i]-temp,0);//第i只怪兽血量
        }
        return num+A[0];//第0只怪兽有剩余血量则要加上
    }
    
};

Java版本

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个怪兽
     * @param A int整型一维数组 A数组代表每个怪兽的血量
     * @return int整型
     */
    public int slove (int n, int[] A) {
        // write code here、
        if(n<3||n%2==0)return -1;//偶数或者小于3都无法使用组合拳
        int num=0;
        for(int i=(n-1)/2-1;i>=0;i--){//从中间开始
            int temp=Math.max(A[2*i+1],A[2*i+2]);//取2*i+1和2*+2的最大值，较小的也会消耗到0
            num+=temp;
            A[i]=Math.max(A[i]-temp,0);//第i只怪兽血量
        }
        return num+A[0];//第0只怪兽有剩余血量则要加上
    }
}

复杂度：

• 时间复杂度：$O(n)O(n)$,至少循环n/2-1次
• 空间复杂度：$O(1)O(1)$，额外变量的空间复杂度为常数级

方法二：递归

可以将方法一中的递推转化为递归，递归的每一层操作是相同的，都是取A[2i+1],A[2i+2]的最大值，累计组合拳数，更新A[i],直到达到递归结束条件i<0,加上A[0]的剩余血量

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个怪兽
     * @param A int整型vector A数组代表每个怪兽的血量
     * @return int整型
     */
    int res=0;
    int slove(int n, vector<int>& A) {
        // write code here
        if(n<3||n%2==0)return -1;//偶数或者小于3都无法使用组合拳
        dfs(n/2-1,A);
        return res;
    }
    void dfs(int i,vector<int>&A){
        if(i<0){//递归结束条件,i可以取到0,当i小于0时加上A[0]的剩余血量
            res+=A[0];
            return;
        }
        int temp=max(A[2*i+1],A[2*i+2]);
        res+=temp;
        A[i]=max(A[i]-temp,0);
        dfs(i-1,A);
    }
};

Java版本

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个怪兽
     * @param A int整型一维数组 A数组代表每个怪兽的血量
     * @return int整型
     */
    int res=0;
    public int slove (int n, int[] A) {
        // write code here、
        if(n<3||n%2==0)return -1;//偶数或者小于3都无法使用组合拳
        dfs(n/2-1,A);
        return res;
    }
    void dfs(int i,int[]A){
        if(i<0){//递归结束条件,i可以取到0,当i小于0时加上A[0]的剩余血量
            res+=A[0];
            return;
        }
        int temp=Math.max(A[2*i+1],A[2*i+2]);
        res+=temp;
        A[i]=Math.max(A[i]-temp,0);
        dfs(i-1,A);
    }
}

复杂度：

• 时间复杂度：$O(n)O(n)$,递归深度为n/2，每层的时间复杂度为常数级
• 空间复杂度：$O(n)O(n)$,递归运行时栈的大小不超过n/2