【深基16.例1】淘汰赛

题目描述

有 $2^n$（$n\le 7$）个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？

输入格式

第一行一个整数 $n$，表示一共 $2^n$ 个国家参赛。

第二行 $2^n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的国家的能力值（$1\le i\le 2^n$）。

数据保证不存在平局。

输出格式

仅一个整数，表示亚军国家的编号。

样例 #1

样例输入 #1

3
4 2 3 1 10 5 9 7

样例输出 #1

1

---

思路

使用一个 pair 类型来表示队伍的编号和实力值。使用一个队列 qu 来表示参赛队伍。首先，根据输入的实力值，依次创建 pair 对象并加入队列中。

使用一个 while 循环，直到队列中只剩一个队伍为止。在每次循环中，从队列中取出两个队伍 a 和 b 进行比较。将实力值较低的队伍 second 记录下来，并将实力值较高的队伍重新加入队列中。

重复此过程直到队列中只剩一个队伍，此时 second 记录的就是最后淘汰的队伍编号，即亚军国家的编号。

---

AC代码

#include <iostream>
#include <cmath>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;struct Steam
{int n;int w;bool operator>(const Steam &x){return this->w > x.w;}
};int main()
{int n;queue<Steam> qu;cin >> n;for (int i = 1; i <= pow(2, n); i++){int w;cin >> w;Steam *team = new Steam();team->n = i;team->w = w;qu.push(*team);}Steam second;while (qu.size() > 1){Steam a, b;a = qu.front();qu.pop();b = qu.front();qu.pop();if (a > b){second = b;qu.push(a);}else{second = a;qu.push(b);}}cout << second.n << endl;return 0;
}