牛牛打怪兽题解

题解一

对于这道题目首先我们发现
1.2*X+1一定是一个奇数，那么显然我们对于有偶数个怪兽，我们肯定是打不死的
2.如果n<3,我们也肯定打不死所有怪兽
3.那么我们怎么做？
考虑一下贪心，我们可以从右往左思考，最右边的只能通过左边把它打死，那么我们从右往左遍历过去，如果右边的还没死，我们根据它的奇偶性找到使用组合技能的三个怪兽，给他们分别扣血即可。
4.注意一下，扣血的时候如果需要一次性扣完，不能一滴一滴扣那样会超时的。
时间复杂度O（n），空间复杂度O（n）

class Solution {
public:
    /**
     * 请你通过solve函数输出最后的答案
     * @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;}
        long long  ans=0;
        for (int i=n-1; i>=0; i--)
        {
            if (A[i]>0)
            {
                long long  t=A[i];
                if((i+1)&1) {
                    A[i]-=t;
                    if (i-1>=0) A[i-1]-=t;
                    if (((i-1)>>1)>=0) A[(i-1)>>1]-=t;
                }
                else {
                    A[i]-=t;
                    A[i+1]-=t;
                    A[i>>1]-=t;
                }
                ans+=t;
            }
        }
        return ans;
        }
};

题解二

首先读者应该能判断出偶数个是不行的，小于三个数也是不行的，小于三个的很好说，因为他放组合拳至少需要三个人。偶数为什么不行呢，因为2*X+1一定是一个奇数。
例如：
[1 2 3 4 5 6]

始终有一个数是打不到的，这个例子中，1可以打2和3，2可以打4和5，6就没办法了

如果是奇数的话，每个数都是可以打到的
例如：
[1 2 3 4 5 6 7]

1可以打2和3,2可以打4和5，3可以打6和6

分析完这个之后，怎么打才能最小化出拳次数呢？首先我们注意到6和7只能由3来打，也就是说，要把6和7打掉，3这个位置至少要出拳min(a[6],a[7])次。同理4和5只能由2来打，也就是说，要把4和5打掉，2这个位置至少要出拳min(a[4],a[5])次。
这个时候，[4,7]已经被完全打掉，这个时候2和3都还可能有剩，所以要一起被1打掉最好，而不用再向后打。
所以我们从后往前遍历，每次考虑两个数，必选使用两个数中的最大值那么多次的次数才能打掉，出拳的位置也相应的减少。

class Solution {
public:
    /**
     * 请你通过solve函数输出最后的答案
     * @param n int整型 n个怪兽
     * @param A int整型vector A数组代表每个怪兽的血量
     * @return int整型
     */
    int slove(int n, vector<int>& A) {
        // write code here
        if(n%2==0||n<3) return -1;
        int ret=0;
        for(int i=n-2;i>0;i-=2)
        {
            ret+=max(0,max(A[i],A[i+1]));
            A[i/2]-=max(0,max(A[i],A[i+1]));
        }
        return ret+=max(0,A[0]);
    }
};