AcWing 1240. 完全二叉树的权值

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

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

作者：

_清醒 , 2020-02-14 18:07:52 , 所有人可见 , 阅读 6809

37

4

#include <iostream>

using namespace std;
const int N = 100000 + 10;

long long q[N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <=n; i++) 
        cin >> q[i];
    int max_ = -1e18;
    /*
    完全二叉树 每层的开头为   2^(n-1) 结尾则是 2^n - 1
    计算每层的数值只需要两个positioner 分别指向开头和结尾
    */
    int depth = 1;
    int res = 1;
    for(int i = 1; i <= n; i *= 2){
        long long s = 0;
        for(int j = i;  j <=  i*2 - 1 && j <= n; j ++) {
            s += q[j];
        }
        if(s > max_) {
            max_ = s;
            res = depth;
        }
        depth++;
    }
    cout << res;
}

19 评论

命不该绝 2023-02-26 09:02

死活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;
}

skyoung 2023-03-06 15:07

最后一次可能到不了2的正数次方应该加判断ant == n - 1

未泯 2023-04-05 20:32 回复了 skyoung 的评论

nb,真是这样，为啥要判断呀

skyoung 2023-04-05 20:54 回复了未泯的评论

因为他是完全二叉树而不是满二叉树，最后一层的节点可能不是满的。如果不加的话你最后一层就可能不会进入最大值的判断

heihei1 2022-04-21 11:07

想知道为什么第二层for循环必须写 j <= n，这不是恒成立吗？

wanttobe 2022-11-01 15:43

过一下脑子。。。谢谢

chid 2022-11-16 11:41

完全二叉树不是满二叉树

blueecho 2022-03-31 16:10

# 妙

hollowknight_3 9个月前

’‘’
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;

const int N = 1e6 + 10;
int res[N];

int main() {
int n;
memset(res, 0, sizeof(res));
scanf(“%d”, &n);
int ans = -0x3f3f3f3f;
int ed = 2, L = 0, a;
for (int i = 1; i <= n; i) {
if (i == ed) {
ed = ed * 2;
L;
}
scanf(“%d”, &a);
res[L] += a;
}
for (int i = 0; i <= L; i++) {
if (ans == -0x3f3f3f3f) {
ans = 0;
continue;
} else if (res[ans] < res[i]) {
ans = i;
}
}
cout << ans + 1 << endl;
}
‘’‘

hollowknight_3 9个月前

#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;

const int N = 1e6 + 10;
int res[N];

多米尼克領主的致意 2023-12-05 14:41

9/12求指点

#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int n;
LL mx = -10e9;
int cnt = 1;
int res;
int no, a[N];
int depth[N];

int main() {
    cin >> n;
    int x = n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i <= n; i++) {
        int y = pow(2, i);
        if (x - y > 0) {
            x -= y;
            cnt ++;
            //cout << cnt << " " << x << endl;
        }
        else break;
    }

    for (int i = 1; i <= cnt; i++) {
        int l = pow(2, i - 1);
        for (int j = 1; j <= l; j ++) {
            depth[i] += a[j + no];
        }
        no += l;
    }

    for (int i = 1; i <= cnt; i++) {
        if (depth[i] > mx) {
            mx = depth[i];//注意负数
            res = i;
        }
    }
    cout << res;
    return 0;
}

hanhyojoo 2023-12-01 00:05

#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;

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