3014: 【普及/提高-】【P4715】淘汰赛
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：13
解决：3
题目描述
有 （）个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？
输入
第一行一个整数 ，表示一共 个国家参赛。
第二行 个整数，第 个整数表示编号为 的国家的能力值（）。
数据保证不存在平局。
输出
仅一个整数，表示亚军国家的编号。
样例输入 复制
3
4 2 3 1 10 5 9 7样例输出 复制
1提示
#include<bits/stdc++.h>
using namespace std;
int value[260],winner[260];
int n;
void dfs(int x) {
if (x>=(1<<n)) return; //如果是叶子结点就不要继续遍历下去了
else {
dfs(2*x); //遍历左子树
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];
}
}
}
int main(){
cin>>n;
for (int i=0;i<(1<<n);i++) { //读入各个结点的能力值
cin>>value[i+(1<<n)]; //叶子结点的获胜方就是自己国家的编号
winner[i+(1<<n)]=i+1;
}
dfs(1); //从根结点开始遍历
cout<<(value[2]>value[3]?winner[3]:winner[2]); //找亚军
return 0;
}