NC564 题解 | #牛牛打怪兽#

题意分析

1-n个位置，每个位置有一个怪兽，每个位置上的怪兽有一个血量，每攻击一个怪兽依次这个怪物会掉一滴血。牛牛攻击在第i个位置的怪兽的时候，会连带攻击到怪物i+i和i+i+1的位置的怪兽。但是只有i+i和i+i+1都在范围1-n之间才能执行这次的攻击的操作。问最少执行多少次操作才能将所有的怪兽都打败（怪兽打败是怪兽的血量为0，同时对怪兽血量为0的怪兽还能继续进行攻击操作)如果不能实现，那么返回-1

思路分析

这是一个贪心的题目，我们先来分析一下哪些是-1的情况，我们发现，如果n<3，那么不能执行任何攻击的操作，返回-1，否则如果输入的n是偶数，那么最后的那个位置是无论如何都不能被攻击到的。这种情况也是返回-1.那么就只剩下大于2的奇数的情况是一定可以做到的。
然后，我们通过进一步分析可以发现，如果想让最后的那个位置的怪兽被打败的操作方法其实是有限的，只能通过对(n-1)/2的位置进行攻击，然后利用连带攻击才能将他打败。所以我们需要从(n-1)/2后面往前面倒序枚举进行贪心的操作。优先确保越靠后的怪兽被打败，然后往前递推。每次维护取 $m a x (a [i + i], [i + i + 1])$ 累加到答案里面即可。

alt

这里我用了两种语言实现,由于给的数组的下标是从0开始，所以下标相应左移一位
- 需要从n/2-1往前进行枚举，总的时间复杂度为 $O (n)$
- 在枚举的过程中只用了少数几个变量进行存储，空间复杂度为 $O (n)$

写法一 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
        // 特判-1的情况和偶数的情况
        if(n<=2||n%2==0){
            return -1;
        }
        
        int ans=0;
        // 我们先找到最右边可以打怪兽的为止，在这右边的都不能直接被打
        // 只能通过x打到2x,2x+1
        for(int i=n/2-1;i>=0;i--){
            // 越靠右边的选择越少，所以我们应该在当前这个为止保证把相关的怪兽都打死，
            // 不然后面就都打不死了,所以我们找到可以关联的两个位置中最大的即可
            // 注意下标是从1开始的
            int mx=max(A[i+i+1],A[i+i+2]);
            ans+=mx;
            A[i]=max(0,A[i]-mx);
        }
        
        // 特判一下第一个位置是否为0
        ans+=A[0];
        
        return ans;
    }
};

写法二 GO

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 n个怪兽
 * @param A int整型一维数组 A数组代表每个怪兽的血量
 * @return int整型
*/
func slove( n int ,  A []int ) int {
    // write code here
    // 特判奇数和偶数的情况
    if(n<=2||n%2==0){
        return -1
    }
    
    ans := 0
    // 我们先找到最右边可以打怪兽的为止，在这右边的都不能直接被打
   // 只能通过x打到2x,2x+1
    for i := n/2 - 1; i >= 0; i-- {
        mx := 0
        // 越靠右边的选择越少，所以我们应该在当前这个为止保证把相关的怪兽都打死，
       // 不然后面就都打不死了,所以我们找到可以关联的两个位置中最大的即可
        // 注意下标是从1开始的
        if A[i+i+1] >= A[i+i+2] {
            mx = A[i+i+1]
        }else{
            mx = A[i+i+2]
        }
        ans += mx
        A[i] -= mx
        if A[i] < 0 {
            A[i] = 0
        }
    }
    
    // 记得加上第一个位置的剩余需要操作的次数
    ans += A[0]
    
    return ans
}