上鏈接：【深基16.例1】淘汰賽 - 洛谷https://www.luogu.com.cn/problem/P4715

上題干：

題目描述

有 2^n（n≤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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
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];
}