AcWing 1240. 完全二叉树的权值
原题链接
简单
作者:
两生
,
2023-01-10 17:06:06
,
所有人可见
,
阅读 97
import java.io.*;
import java.util.StringTokenizer;
public class Main{
static int N = 100010;
static int a[] = new int[N];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer strInput = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++) a[i] = Integer.parseInt(strInput.nextToken());
long s = 0, max = -(1<<30), k = 1;
for(int i = 1, d = 1; i <= n; i *= 2, d++){
for(int j = i; j < i + (1 << (d-1)) && j <= n; j++) s += a[j]; // 计算深度d内的权值和
// 判断更新max和k
if(max < s){
max = s;
k = d;
}
s = 0; // 重置某一深度内的权值和
}
System.out.println(k);
br.close();
}
}