理解与感悟
1、数据结构为数组,保存完美二叉树。
2、完美二叉树的固定的位置记录,可以方便找到左儿子,右儿子。
3、如果树的高度为\(h\),那么结点的个数为\(2^h-1\)个。这个就是个二进制数的表示法,所有小哥的和,等于大哥的力量减1.
4、国家的概念不重要,国家的概念只是整体数据结构“比赛树”的叶子结点。
5、递归用于完美二叉树很有用,可以直接递归根,根依赖于左右子树,如果左右子树完成了填充,那么对比一下就知道谁是冠军,并且全部填充完毕后,就知道了亚军和季军。
#include <bits/stdc++.h>
using namespace std;
const int N = 260;
int value[N]; //记录该子树获胜者的实力值
int winner[N];//记录该子树获胜者
//本题n的概念很奇葩,不是n个国家,是2^n个国家~,比如n=3,就是2^3个国家,即8个国家。
int n;
//函数定义:计算x结点的获胜者
void dfs(int x) {
//叶子结点
if (x >= (1 << n)) return;//啥也不用干,因为手动填充干净了,递归出口
//填充左子树,填充右子树
dfs(2 * x), dfs(2 * x + 1);
//左结点值,右结点值
int lvalue = value[2 * x], rvalue = value[2 * x + 1];
//pk,谁大就更新成谁的
if (lvalue > rvalue) value[x] = lvalue, winner[x] = winner[2 * x];
else value[x] = rvalue, winner[x] = winner[2 * x + 1];
}
/**
测试用例:
3
4 2 3 1 10 5 9 7
*/
int main() {
cin >> n;
//填充叶子结点,共2^n个
for (int i = 0; i < (1 << n); i++) {//完美二叉树结点个数 2^n
//计算出叶子结点的下标,数组下标从1开始
int k = i + (1 << n); // 比如本题用例就是8,9,10,11,12,13,14,15,共8=2^3个
cin >> value[k]; //读入各个结点的能力值
winner[k] = i + 1; //叶子结点的获胜方就是自己国家的编号
}
//从根结点开始遍历,填充整个世界杯的成绩结果树
dfs(1);
//找亚军
cout << ((value[2] > value[3]) ? winner[3] : winner[2]) << endl;
return 0;
}