题解 | #牛牛打怪兽#
牛牛打怪兽
http://www.nowcoder.com/practice/a3b055dd672245a3a6e2f759c237e449
思路：
根据题目要求打第X怪兽的时候，同时会打到第2X、2X+1这两个怪兽，组合拳必须攻击三只怪兽,可以得到以下结论：
怪兽数量至少3只、怪兽数量是奇数。
那么要想打到最后一只怪兽(A[n-1])，就得对A[n/2-3/2]打拳，这样可以保证满足题目要求。
于是我们可以从A[n/2-3/2]开始，往前遍历，对A[n/2-3/2]的打拳数量应该是A[n-1]和A[n-2]中较大数的值。这样才能保证把两个都打死。(注：下标的倍数关系是打A[i]的同时会打到A[2i+1],A[2i+2])
所以可以用一个for循环，i从n/2-1开始递减，直到i=0停止。A[i]被打的次数(tmp)就是A[2i+1]和A[2i+2]中较大的数，然后更新A[i]的值（这里的更新是指A[i]有可能没被打死，那么就要比较0和A[i]-tmp的大小）,res累加tmp即可，最后返回值的时候只要加上A[0]，也就是第1只怪兽的剩余血量。
代码如下
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 n个怪兽
* @param A int整型vector A数组代表每个怪兽的血量
* @return int整型
*/
int slove(int n, vector<int>& A) {
// write code here
int res = 0;
if((n<=2) || !(n%2))
return -1;//必须打三只以上怪兽，n必须是奇数
for(int i=n/2-3/2;i>=0;i--)
{
int tmp = max(A[2*i+1],A[2*i+2]);
A[i] =max(0, A[i]-tmp);
res += tmp;
}
return res+A[0];
}
};牛客刷题记录 文章被收录于专栏
记录自己的刷题记录，刷过的题的解法
查看13道真题和解析
