P4715 【深基16.例1】淘汰赛 题解
题目链接
这个题目出得很好，有树的影子。但是我看了看题解，感觉代码有点复杂。对于这道题，我们可以利用存树的思想，利用上传的操作进行反推，代码不超过16行还可以再压压行。
我们先看图解，就拿样例来说：
input:
3
4 2 3 1 10 5 9 7
output:
1这是一个什么样的过程呢?
首先，他们的初始状态是这样的：
经过第一次操作（比赛）后，关系变成了这样，
我们再拿这几个数比较，进行下一次操作（比赛），关系如图，只剩下
进行最后一次操作（比赛），虽然已经不重要了，图示如下：
这样就是一颗很完美的树了，每一个节点的数值都是由他的两个儿子所决定的，即儿子决定父亲的值。我们通过这种关系，能够轻易得出我们要的答案。
所以，我们怎么去实现这个过程呢？
-知识储备：我们需要树的知识，我们如何去存储一个树呢？其实，父亲和他的儿子是有特定关系的：
如果还不明白，看下面这张图：
再说一遍思路：
用儿子推出父亲！
- 我们先把儿子存起来，而且是存在树的最底部，总共有
2^n 个数，我们从2^n 存起：
n=pow(2,n);
for(int i=n;i<=2*n-1;i++)
cin>>tree[i];- 然后，用儿子推出父亲，
父亲=max(左儿子，右儿子)
for(int i=n-1;i>=0;i--)
tree[i]=max(tree[i*2],tree[i*2+1]);- 这样，这棵树的所以节点我们就都知道了，题目要求我们要第二名，第二名就是树的二层两个树中的最小值：
ans=min(tree[2],tree[3]);- 最后，他要的是第二名的下标，我们需要从
2^n 开始，重新遍历一遍最后一层，寻找到了下标，我们就需要输出（i-n+1) ：
for(int i=n;i<=2*n-1;i++)
if(tree[i]==ans)
cout<<i-n+1;最终代码：
#include<bits/stdc++.h>
using namespace std;
int n,tree[500];
int main(){
cin>>n;
n=pow(2,n);
for(int i=n;i<=2*n-1;i++)
cin>>tree[i];
for(int i=n-1;i>=0;i--)
tree[i]=max(tree[i*2],tree[i*2+1]);
int ans=min(tree[2],tree[3]);
for(int i=n;i<=2*n-1;i++)
if(tree[i]==ans)
cout<<i-n+1;
return 0;
}