48 lines
1.8 KiB
C++
48 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
//2^7是极大值，就是 128是队伍的最大值，完全二叉树的最底层是128，上面肯定是127个，加在一起是255个，声明一个大于255的数字N可以保存的下
|
||
const int N = 260;
|
||
int value[N]; //每队伍的能力值
|
||
int winner[N]; //胜利者的队伍编号
|
||
int n; //n支队伍
|
||
|
||
//遍历完美二叉树
|
||
void dfs(int x) {
|
||
//如果已经完成了所有队伍的比较，返回
|
||
if (x >= 1 << n) return;
|
||
//左子树,完成左侧value数组与winner数组的填充
|
||
dfs(2 * x);
|
||
//右子树,完成右侧value数组与winner数组的填充
|
||
dfs(2 * x + 1);
|
||
//填充完毕后，可以大胆的使用了~
|
||
int lvalue = value[2 * x], rvalue = value[2 * x + 1];
|
||
//如果左结点获胜
|
||
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() {
|
||
//2^n次的n,用例是3，表示2^3=8，8支队伍参加
|
||
cin >> n;
|
||
//读入
|
||
int m = 1 << n; //到底是几支球队？
|
||
for (int i = 0; i < m; i++) {
|
||
cin >> value[i + m]; //读入各个节点的能力值,为什么要i+m呢？因为完美二叉树的保存方法决定的。以n=3为例，手画一下数据的保存方式秒懂。
|
||
winner[i + m] = i + 1;//叶子结点的获胜方就是自己国家的编号,相当于初始化数据，没有别人比赛之前，获胜者是自己
|
||
}
|
||
dfs(1);//从根结点开始遍历,遍历每个节点
|
||
|
||
cout << (value[2] > value[3] ? winner[3] : winner[2]);//找亚军
|
||
return 0;
|
||
} |