宁波网站设计企业,常用的小企业网站建设,wordpress 页面与文章,高明专业网站建设报价上链接#xff1a;【深基16.例1】淘汰赛 - 洛谷https://www.luogu.com.cn/problem/P4715
上题干#xff1a; 题目描述 有 2^n#xff08;n≤7#xff09;个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值#xff0c;且都不相等。能力值高的国家和能力值…上链接【深基16.例1】淘汰赛 - 洛谷https://www.luogu.com.cn/problem/P4715
上题干 题目描述 有 2^nn≤7个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛胜者晋级。3 号国家和 4 号国家也踢一场胜者晋级……晋级后的国家用相同的方法继续完成赛程直到决出冠军。给出各个国家的能力值请问亚军是哪个国家 输入格式 第一行一个整数 n表示一共 2^n 个国家参赛。 第二行 2^n 个整数第 i 个整数表示编号为 i 的国家的能力值1≤i≤2^n。 数据保证不存在平局。 输出格式 仅一个整数表示亚军国家的编号。 输入输出样例 输入 #1复制 3
4 2 3 1 10 5 9 7输出 #1复制 1 写这道题我们可以先将题目给的样例画出来。大概是这样的 我们可以发现从最顶部的冠军开始二叉树的根结点它的在下一层有两个国家分支而且每个国家的下面又有两个国家。直到达到最底部叶节点没有分支了。
每个结点的左右两边叫做左子树右子树。每个左子树右子树又是一个二叉树这样的结构就是满二叉树。
我们可以画出这道题的满二叉树的图像 根据这两张图我们就可以写出这道题。
首先我们把所有的数值放进二叉树的叶结点也就是最下面一层。
定义一个战斗力数组 able[N],N的取值取决于数据范围。
然后存入每个国家的战斗力由我们的第一张图可知8的位置是国家1,9的位置是国家2以此类推。和每个国家的编号。
然后存入之后开始dfs
直到遍历到从树的底部的上一层该结点的左右子树。如图 if(该数的左结点战斗力右结点) 该数的战斗力就是 左结点战斗力该数的编号就是左节点的编号。
以此类推直到遍历 所有结点。
最后在比较结点2结点3的战斗力就可以得到亚军的编号。
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecmath
#includestring
#includecstring
#includestring
#includealgorithm
#includevector
#includecctype
#includemap
#includeset
#includequeue
using namespace std;
const int N 1e5;
int able[N];
int win[N];
int n;
void dfs(int x)
{if (x 1 n)return;else {dfs(2 * x);dfs(2 * x 1);int left 2 * x, right 2 * x 1;if (able[left] able[right]) {able[x] able[left];win[x] win[left];}else {able[x] able[right];win[x] win[ right];}}
}
int main()
{cin n;for (int i 0; i 1 n; i){cin able[i (1 n)];win[i (1 n)] i 1;}dfs(1);able[2] able[3] ? cout win[2] : cout win[3];
}
