历届真题 完全二叉树的权值【第十届】【省赛】【A组】 java

没仔细学过二叉树，写麻烦了。。

AC代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N+1];
        int[] sum = new int[N+1];
        //前缀和
        for(int i = 1;i<=N;i++){
            nums[i] = sc.nextInt();
            sum[i] = sum[i-1] + nums[i];
        }

        double pos = N+1;
        int ks = (int) (Math.log(pos)/Math.log(2));
        int id = (int) (Math.pow(2,ks) - 1);
        int later = sum[N] - sum[id];
        int max = later;
        int ans = ks+1;
        while(id > 1){
            double l = id + 1 ;
            int k = (int) (Math.log(l)/Math.log(2));//深度
            int x = (int) Math.pow(2,k-1);
            int j = id - x;
            if(sum[id]-sum[j] >= max){
                max = sum[id]-sum[j];
                ans = k;
            }
            id = j;
        }
        if(nums[1] >= max){
            ans = 1;
        }
        System.out.println(ans);
    }
}