题目描述
有 2^n(n\le7)2n(n≤7) 个国家参加世界杯决赛圈且进入淘汰赛环节。我经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？
输入格式
无
输出格式
无
输入输出样例
输入 #1复制
3 4 2 3 1 10 5 9 7
输出 #1复制
1
当然这道题目有更简单的解法，但是因为在写这道题目的时候很自然的把这个比赛的逻辑关系画了出来就想到了刚刚总结的线段树，进行了一下变形，把父结点存成了两个儿子的最大值
#include <iostream>
using namespace std;
typedef long long ll;
struct Node{ll val,id;
};
Node a[150],tree[600]; //一般为了防爆，线段树开比数组大四倍空间
Node maxtree(Node lfnode,Node rinode)
{return lfnode.val>rinode.val?lfnode:rinode;
}
Node mintree(Node lfnode,Node rinode)
{return lfnode.val>rinode.val?rinode:lfnode;
}
void built(ll node,ll start,ll end)
{if(start==end){tree[node]=a[start];return;}ll lfnode=node*2;ll rinode=node*2+1;ll mid=(start+end)/2;built(lfnode,start,mid);built(rinode,mid+1,end);tree[node]=maxtree(tree[lfnode],tree[rinode]);
}
int main()
{ll n;cin>>n;ll len=1<<n;for(ll i=1;i<=len;i++){cin>>a[i].val;a[i].id=i;}built(1,1,len); //建树cout<<mintree(tree[2],tree[3]).id<<endl;return 0;
}