返回题解分享
讨论 / 题解分享/ 帖子详情

完全二叉树的权值(编程题) - 题解

被气晕了, 忘记特殊情况交了12次才通过

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	static int n;
	static int a[];

	public static void main(String[] args) {
		Scanner scanner = new Scanner(new BufferedInputStream(System.in));
		PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

		n = scanner.nextInt();

		a = new int[n];

		for (int i = 0; i < n; i++) {
			a[i] = scanner.nextInt();
		}
		double end = Math.log(n + 1) / Math.log(2);

		int res = 1;
		long maxCount = 0x3f3f3f;
		maxCount = -maxCount;
		int index = 0;
		for (int dep = 1; dep <= end; dep++) {
			long sum = 0;

			for (int i = 1; i <= Math.pow(2, dep - 1); i++) {
				sum += a[index++];
			}
			if (sum > maxCount) {
				res = dep;
				maxCount = sum;
			}
		}
//特别情况,剩余的节点单独记录
		long sum = 0;
		while (index < n) {
			sum += a[index++];
		}
		if (sum > maxCount) {
			res = (int)end+1;
			maxCount = sum;
		}

		System.out.println(res);

		writer.flush();
		scanner.close();
	}

}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!