现在牛牛面前有n只怪兽,第i只怪兽的血量为ai。牛牛刚刚从牛毕哪里学到一套组合拳
当使用这个组合拳的时候,打第X怪兽的时候,同时会打到第2X、2X+1这两个怪兽,每次组合拳会扣打到的怪兽一滴血。一个怪兽血量为0即为死亡,同时组合拳是可以鞭尸的,这意味着即使怪兽死亡,也可以对其使用组合拳。
值得注意的是组合拳必须攻击三只怪兽。
牛牛想知道它需要使用最少多少次组合拳才能把所有怪兽打死,如果打不死请输出-1。
现在牛牛面前有n只怪兽,第i只怪兽的血量为ai。牛牛刚刚从牛毕哪里学到一套组合拳
牛牛想知道它需要使用最少多少次组合拳才能把所有怪兽打死,如果打不死请输出-1。
2,[1,2]
-1
因为组合拳至少要打到三个怪兽,所以组合拳放不出来
3,[1,2,3]
3
至少要对1号怪兽打三次组合拳
怪兽编号1—NA[0]代表1号怪兽血量A[1]代表2号怪兽血量....依次类推
class Solution { public: /** * 请你通过solve函数输出最后的答案 * @param n int整型 n个怪兽 * @param A int整型vector A数组代表每个怪兽的血量 * @return int整型 */ int slove(int n, vector<int>& A) { int s = 0, t = 0; if(n<=2 || (n&1)==0) return -1; else{ for(int i=n/2-1;i>=0;i--){ t = max(A[2*i+1], A[2*i+2]); A[i] = max(0, A[i]-t); s += t; } s += A[0]; } return s; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 n个怪兽 * @param A int整型vector A数组代表每个怪兽的血量 * @return int整型 */ int slove(int n, vector<int> &A) { int ans = 0; if (n < 3 || n % 2 == 0) { return -1; } int i = (n - 1) / 2, i2 = n - 1, i3 = n; // 分别是第X,第2X,第2X+1个 for (; i > 0; i--) { i2 = i * 2; i3 = i * 2 + 1; int res = max(A[i2 - 1], A[i3 - 1]); if (res > 0) { ans += res; A[i2 - 1] -= res; A[i3 - 1] -= res; A[i - 1] -= res; } } if (A[0] > 0) { ans += A[0]; } return ans; } };