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

闲话

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

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

分半区

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

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

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

所以我们现在要把冠军（能力最大值）所在的半区去掉，然后把另外一个半区的最强队伍找出来，就可以找到亚军了。
注意：亚军不是全部

2^n

支球队的次强队伍，而是另外一个半区的最强队伍。因为次强队伍可能被最强队伍在决赛之前打败了。而没能闯进决赛的队伍一定不是冠军或亚军。

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

代码

CPP

#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;
}

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

文章操作

闲话

分半区

代码

相关推荐

评论

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