P4715题解

orifi · 2021-07-03 21:29:06 · 个人记录

P4715题解

思路

这道题可以将国家分成两个部分，左部分和右部分。

左部分取最大值就是左部分的冠军，右部分最大值就是右部分冠军。

而最大值可以在输入中求出来。

代码

#include<bits/stdc++.h>
using namespace std;
int m,a;
int max1,max2,maxi1,maxi2;
int main()
{
    cin>>m;
    int n=1<<m;//计算国家数
    for(int i=1; i<=n; i++)
    {
        cin>>a;//读入每个国家能力值
        if(i<=n/2)
        {
            if(a>max1)
            {
                max1=a;//保存左部分能力值最大值
                maxi1=i;//保存左部分能力值最大值的编号
            }
        }
        else
        {
            if(a>max2)
            {
                max2=a;//保存右部分能力值最大值
                maxi2=i;//保存右部分能力值最大值的编号
            }
        }
    }
    cout<<(max1<max2?maxi1:maxi2);//三目运算输出答案
    return 0;
}

时间复杂度:O(2^M)。

鼓掌