P4715 【深基16.例1】淘汰赛 【三种方法】
题目描述
有 2^n(n\le7)2n(n≤7) 个国家参加世界杯决赛圈且进入淘汰赛环节。我经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？
输入格式
无
输出格式
无
输入输出样例
输入 #1
3
4 2 3 1 10 5 9 7
输出 #1
1
方法一：二叉树
先相邻的两两求最大值，再把这些最大值重复操作，直到最后为止。
#include
#include
#include
#include
using namespace std;
struct node{
int power;
int id;
}tree[1000],a[200];
int N;
void buildtree(int index,int start,int end){
if(start==end){
tree[index]=a[start];
return ;
}
int l=index*2;//左子树节点下标
int r=index*2+1;//右子树节点下标
int mid=(start+end)/2;
buildtree(l,start,mid);
buildtree(r,mid+1,end);
tree[index].power=max(tree[l].power,tree[r].power);
if(tree[index].power==tree[l].power) tree[index].id=tree[l].id;
if(tree[index].power==tree[r].power) tree[index].id=tree[r].id;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=pow(2,n);i++){
cin>>a[i].power;
a[i].id=i;
}
int num=pow(2,n);
buildtree(1,1,num);
int Min=min(tree[2].power,tree[3].power);
if(Min==tree[2].power) cout< if(Min==tree[3].power) cout< return 0; } 方法二：sort函数直接排序 把 nn 支队伍分成两个区间，一个上半区，一个下半区。那么上半区最强者与下半区最强者，必是一冠一亚。直接 sort 即可 #include #include #include #include #include using namespace std; int main(){ int a[200],b[200],c[200],d[200]; int n;cin>>n; int num=pow(2,n-1); for(int i=0;i cin>>a[i];c[i]=a[i]; } for(int j=0;j cin>>b[j];d[j]=b[j]; } sort(a,a+num); sort(b,b+num); //cout< int Min=min(b[num-1],a[num-1]); for(int i=0;i if(c[i]==Min){ cout< return 0; } } for(int i=0;i if(d[i]==Min){ cout< return 0; } } } 方法三：动态规划 由题意得：可以找出动态规划方程：dp[i][k++]=max(dp[i-1][j],dp[i-1][j+1]) #include #include #include #include #include using namespace std; int dp[10][200]; int main(){ int n; cin>>n;int num=pow(2,n); for(int i=0;i cin>>dp[0][i]; } int k=0; for(int i=1;i<=n;i++){ k=0; for(int j=0;j dp[i][k++]=max(dp[i-1][j],dp[i-1][j+1]); } num=num/2; } int Min=min(dp[n-1][0],dp[n-1][1]); for(int i=0;i if(dp[0][i]==Min){ cout< return 0; } } }