洛谷题单指南-二叉树-P4715 【深基16.例1】淘汰赛

原题链接：https://www.luogu.com.cn/problem/P4715

题意解读：计算亚军得主，注意能力值最高的肯定是冠军，但能力值第二高的不一定是亚军，因为有可能中途就遭遇冠军。

解题思路：

根据题意，两两比赛，一轮后再按顺序两两比赛，形如一棵二叉树，但解题其实用不到二叉树的数据结构

可以看出，最后参与决赛的两个国家，一定是前一半和后一半的第一名，也就是是分别在前一半、后一半国家中能力值最高

问题就好解决了，枚举即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

int a[130], n;

//返回l~r范围内的冠军下标
int match(int l, int r)
{
    int maxx = a[l], maxn = l;
    for(int i = l + 1; i <= r; i++)
    {
        if(a[i] > maxx) 
        {
            maxx = a[i];
            maxn = i;
        }
    }
    return maxn;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= 1 << n; i++)
    {
        cin >> a[i];
    }  
    int l = 1, r = 1 << n;
    int lc = match(l, r / 2); //前一半的冠军
    int rc = match(r / 2 + 1, r); //后一半的冠军
    if(a[lc] < a[rc]) cout << lc;
    else cout << rc;

    return 0;
}