P4715 【深基16.例1】淘汰赛

这题其实是二叉树左子树和右子树之间的比较，可以使用队列来不断求值，亦可以找出左右部分最大值，比较得出亚军。

题解 P4715 【深基16.例1】淘汰赛 - 洛谷专栏 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <queue>


using namespace std;

typedef long long LL;

typedef pair<int, int> pii;
queue<pii> que;
void solve() {
  int n;
  cin >> n;
  	n=1<<n;	    //	n<<=1  要注意下这里,我这里写错了debug半天，原先写的是将1右移一位即2。
  for (int i = 1; i <= n; i++) {
    int tmp;
    cin >> tmp;
    que.push(make_pair(tmp, i));
  }
  while (que.size() != 2) {
    auto a = que.front();
    que.pop();
    auto b = que.front();
    que.pop();
    if (a.first > b.first) {
      que.push(a);
    } else {
      que.push(b);
    }
  }
  auto a = que.front();
  que.pop();
  auto b = que.front();
  que.pop();
  if (a.first < b.first) {
    cout << a.second << endl;
  } else { 
    cout << b.second << endl;
  }
}

int main() { solve(); }