蓝桥杯2019年第十届省赛真题-完全二叉树的权值

解题思路:

观察二叉树每层的序号

第一层 2的0次方

第二层 2的1次方 到  2的2次方-1
等等

我们可以记录最大值然后求出每层的和，比较如果sum比较大的话同时更新max和每层开头序号maxi即可

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int main() {

int n, a = 1, maxi;

long long max = 1e10 * (-1), sum, t;

cin >> n;

while (true)

{

sum = 0;

for (int i = a; i <=a*2-1 ; i++)

{

cin >> t;

sum += t;

if (i==n) {

if (sum > max) { max = sum; maxi = a; }

goto end;

}

}

if (sum > max) { max = sum; maxi = a; }

a *= 2;

}

end:

cout << log(maxi) / log(2) + 1;  //通过这一层的开头序号求出对应深度

return 0;

}