蓝桥杯第十届省赛试题G:完全二叉树的权值(20分)

题目描述

给定一棵包含 NN 个节点的完全二叉树,树上每个节点都有一个权值,按从 上到下、从左到右的顺序依次是 A_1, A_2, ··· A_NA1​,A2​,⋅⋅⋅AN​,如下图所示:

蓝桥杯第十届省赛试题G:完全二叉树的权值(20分)

现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点 权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。

注:根的深度是 1。

输入描述

第一行包含一个整数 N(1 \leq N \leq 10^5)N(1≤N≤105)。

第二行包含 NN 个整数 A_1, A_2, ··· A_N (−10^5 \leq A_i \leq 10^5)A1​,A2​,⋅⋅⋅AN​(−105≤Ai​≤105)。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

7
1 6 5 4 3 2 1

输出

2

题解:其实没啥说的,不要一看到二叉树就慌。我feel他只能考你一些规律性的思维题,又不会让你写一个遍历二叉树吧??? 

就是一个都把2的n次方-1存起来,然后都加起来存到数组里,然后找第一个最大值就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100005];
int summ[17];
long long sum;
int n;
vector<ll> v[17];
int x[20];
int main()
{
    //2的17次方超100000
    for (int i = 1; i <= 18; i++)
    {
        x[i] = (1 << (i - 1));
    }
    cin >> n;
    int k;
    int t = n;
    for (int i = 1; i <= 18; i++)
    {
        t -= x[i];
        if (t <= 0)
        {
            t += x[i];
            k = i;
            break;
        }
    }
    // for (int i = 1; i <= 16; i++)
    // {
    //     if ((1 << i) - 1 == n)
    //     {
    //         k = i;
    //         break;
    //     }
    // } k不能这么求,是完全二叉树,不是满二叉树

    for (int i = 0; i < k - 1; i++)
    {
        for (int j = 1; j <= (1 << i); j++)
        {
            ll value;
            cin >> value;
            v[i].push_back(value);
        }
    }
    for (int j = 1; j <= t; j++)
    {
        ll value;
        cin >> value;
        v[k - 1].push_back(value);
    }
    for (int i = 0; i < k; i++)
    {
        for (auto p : v[i])
        {
            summ[i] += p;
        }
    }
    ll max = INT_MIN;
    for (int i = 0; i < k; i++)
    {
        if (max < summ[i])
        {
            max = summ[i];
        }
    }
    for (int i = 0; i < k; i++)
    {
        if (max == summ[i])
        {
            cout << i + 1;
            return 0;
        }
    }
}

上一篇:四则运算随机出题


下一篇:Vue事件总线(EventBus)使用详细介绍