完全二叉树的权值——19年省赛-阿里云开发者社区

完全二叉树的权值——19年省赛

2023-04-24 47

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 完全二叉树的权值——19年省赛

题目链接：

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

编辑

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

注：根的深度是 1。

输入描述

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅AN。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

7
1 6 5 4 3 2 1

输出

运行限制

最大运行时间：1s
最大运行内存: 256M

JAVA解法：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
                int n = scan.nextInt();
        int []tree = new int[n];
        int []a = new int[10000];
        for(int i = 0;i<tree.length;i++) {
            tree[i] = scan.nextInt();
        }
        int i = 0;
        int sum = 0;
        for(int j = 0;j<tree.length;j++) {
            a[i] += tree[j]; 
            sum++;
            if(sum == Math.pow(2, i)) {
                i++;
                sum = 0;
            }
        }
        int max = a[0];
        for(int x = 0;x<a.length;x++) {
            if(a[x] > max) {
                max = a[x];
            }
        }
        for(int x = 0;x<a.length;x++) {
            if(a[x] == max) {
                System.out.println(x+1);
            }
        }
        scan.close();
    }
}

C++解法：

#include <cstdio>
#include <cmath>
using namespace std;
const int N = 100010;
int a[N];
int main(){
    int n, res, sum = 0, dep = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    res = a[1];
    int e = 1;
    for (int i = 2; i <= n; i++){
        sum += a[i];
        if (pow(2, e + 1) - 1 == i){
            if(sum > res){
                res = sum;
                dep = e + 1;
            }
            sum = 0;
            e ++ ;
        }
    }
    if(sum > res){
        res = sum;
        dep = e + 1;
    }
    printf("%d", dep);
    return 0;
}

文章标签：

Java

C++