P4715 【深基16.例1】淘汰赛 【三种方法】 |
您所在的位置:网站首页 › peerj是哪个国家的 › 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>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 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |