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

#include <iostream>
using namespace std;
const int N = 1000000;
static int A[N];
static int sum[N] = { 0 };
static int Tree[1000][100000] = { 0 };
int main() {
  long long n;
  int t = 0;
  long long k = 1;
  int i;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }
  for (i = 0; t < n ; i++) {
    for (int j = 0; j < k; j++) {
      Tree[i][j] = A[t++];
    }
    k *= 2;//更新层数
  }
  k = 1;
  int maxi = 0, mini = 0;
  for (int l = 0; l < i; l++) {
    for (int j = 0; j < k; j++) {
      sum[l] += Tree[l][j];
    }
    if (sum[maxi] < sum[l]) {
      maxi = l;
    }
    if (sum[mini] > sum[l]) {
      mini = l;
    }
    k *= 2;
  }
  int num = 0;
  for (int l = 0; l < i; l++) {
    if (sum[l] == sum[maxi]) {
      num++;
    }
  }
  if (num < 2) {
    cout << maxi + 1;
  }
  else cout << mini + 1;
  return 0;
}