AcWing 1240. 完全二叉树的权值    原题链接    简单

作者： 作者的头像   cqazy ,  2021-04-03 16:44:36 ,  所有人可见 ,  阅读 1805

10


2

前置：完全二叉树性质

对于第 $i$ 层，保证存在 $2^{i-1}$ 个结点的满二叉树。

题目思路：

对于每一层的和，我们可以用 $h$ 数组进行存储：

$h_1$ = $\sum\limits^{2^{1}-1}_{i=2^{1-1}}(a_i)$

$h_2$ = $\sum\limits^{2^{2}-1}_{i=2^{2-1}}(a_i)$

$h_3$ = $\sum\limits^{2^{3}-1}_{i=2^{3-1}}(a_i)$

$h_4$ = $\sum\limits^{2^{4}-1}_{i=2^{4-1}}(a_i)$

…

是不是发现突然很简单？对于每个 $h_i$，我们可以求 $\sum\limits^{2^{i}-1}_{j=2^{i-1}}(a_j)$ 就行啦！

code： 

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 0x7ffffff;

int n;

int a[1 << 17], h[17];//2^17 > 10^5

signed main() {

    scanf ("%lld", &n);

    for (int i = 1; i <= n; i ++) 
        scanf ("%lld", a + i);
        //读入 ai，因为 n 的大小是 10^5, 所以用 scanf 这类较快的读入方式。

    int i = 1, j = 0;

    while (i <= n) {

        ++ j;

        while (i < pow (2, j)) {//从 2^(j-1) 循环到 2^j-1

            h[j] += a[i ++];
        }
    }

    int maxx = -INF, res = 0;//找最大

    for (i = 1; i <= j; i ++)
        if (h[i] > maxx) 

            maxx = h[i],
            res = i;

    printf ("%lld\n", res);

    return 0;
}

2 评论

用户头像
命不该绝   2023-02-26 09:26      1    踩      回复

死活12过10求指点

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

const int N = 1e5 + 10;
long long n, ant = 0, cnt = 0;
long long res = 0;
long long v[N];
priority_queue<pair<long long, long long>> q;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < n; i++){
        res += v[i];
        ant++;
        if(ant == pow(2, cnt)){
            q.push({res, cnt + 1});
            ant = 0;
            cnt++;
            res = 0;
        }
    }
    cout << q.top().second;
    return 0;
}
用户头像
hanhyojoo   2023-12-01 00:06         踩      回复 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int p[N],q[N];
int main()
{
      int n;
      cin>>n;
      for(int i=1;i<=n;i++)
      cin>>p[i];
      long long  deep=0,maxv=LLONG_MIN;
      for(int i=1;i<=n;)//枚举深度
      {      long long res=0;
             long long  t=2*i;
              deep++;
          while(i<t&&i <= n)
          {      
              res+=p[i];
              i++;
          }
          q[deep]=res;
          maxv=max(maxv,res);
          i=t;
      }
      for(int i=1;i<=deep*2;i++)
          if(q[i]==maxv)
          {cout<<i;
            break;
          }
    return 0;

}
最后一组数据过不去，大佬看一下