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

· · 题解

闲话

上来我就很好奇：为什么不问问冠军呢？ 冠军更厉害啊！
然后发现冠军就是所有能力值的最大值，那就不需要用二叉树了。

然而，事实是，即使是求亚军也和二叉树没多大关系。

分半区

首先奉上一张淘汰赛的图片：

看过球类体育运动赛事淘汰赛制的朋友们一定都知道：冠军和亚军一定属于不同的半区。
拿上图来举例，这次欧洲杯的冠军是西班牙，来自上半区；亚军是英格兰，来自下半区。它们只在决赛相遇。

这也就是说：冠军所在的半区一定没有亚军；亚军一定在另外一个半区。

所以我们现在要把冠军（能力最大值）所在的半区去掉，然后把另外一个半区的最强队伍找出来，就可以找到亚军了。
注意：亚军不是全部 2^n 支球队的次强队伍，而是另外一个半区的最强队伍。因为次强队伍可能被最强队伍在决赛之前打败了。而没能闯进决赛的队伍一定不是冠军或亚军。

仍然拿上图举例：英格兰可能并非整届赛事中的次强队伍，但它一定是下半区的最强队伍。
事实是：按照当时情况来看，法国、德国等队伍都比英格兰更强，但它们都提前遇到了最强的西班牙，所以都在决赛之前倒下，没能成为亚军。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 150;

int n, a[N], maxi = -1, sec = -1, pos, ans;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    // 找到最强队伍作为冠军 
    for(int i=1; i<=pow(2,n); i++){
        cin >> a[i];
        if(a[i] > maxi){
            maxi = a[i];
            pos = i;
        }
    }

    // 假设我们在前半区中找亚军 
    int i = 1, j = pow(2, n-1);
    // 发现冠军在前半区, 只好改为去后半区找亚军 
    if(pos <= pow(2, n-1))
        i = pow(2, n-1) + 1,
        j = pow(2, n);

    // 循环找这个半区的最大值作为亚军 
    for(; i<=j; i++){
        if(a[i] > sec){
            sec = a[i];
            ans = i;
        }
    }

    cout << ans;
}