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

· · 题解

蒟蒻我又来写题解了。

看到yangrunze 大佬用线段树A的，只能%%%了

思路：

  1. 一串2的n次方个的数字，相邻两个互相比较，那么这串数字中最大的那个，一定是冠军。
  2. 但是，这道题让我们求亚军。首先要明白的一个地方是，第二大的数并不一定就是亚军，原因是它有可能与冠军比较，被刷下去了。
  3. 我们可以转换一下思路：把这串数字从中间一分为二。根据1.，一定可以分别求出前面和后面数字中的最大值(设为x，y)，则冠军与亚军一定从x和y中取得(仔细想想，我就不解释了)；然后输出亚军的编号就行了。

话不多说，上代码。亲测AC。

不要直接复制粘贴代码,根据自己的思路打一遍！！

#include<bits/stdc++.h>
using namespace std;
int tmp,n,tmp2,p,ans;
struct cou{
    int en;//每个国家的能量值
    int ta;//每个国家的编号
}a[200];

bool cmp(cou x,cou y)
{
    return x.en>y.en;//对结构体sort排序
}

int main()
{
    cin>>tmp;
    n=pow(2,tmp);
    for(int i=1;i<=n;i++){
        cin>>a[i].en;
        a[i].ta=i;
    }
    sort(a+1,a+n/2+1,cmp);//前一部分国家排序
    sort(a+n/2+1,a+n+1,cmp);//后一部分国家排序
    if(a[1].en>a[n/2+1].en){
        cout<<a[n/2+1].ta;//输出较小能量值的国家的编号
    }
    else{
        cout<<a[1].ta;
    }
    return 0;
}

祝大家AC此题。