【深基16.例1】淘汰赛(上)

题目链接【深基16.例1】淘汰赛 - 洛谷https://www.luogu.com.cn/problem/P4715

 题目描述

        有 2^n(n≤7) 个国家参加世界杯决赛圈且进入淘汰赛环节。已知各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1号国家和2号国家踢一场比赛，胜者晋级。3号国家和4号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？

输入

第一行一个整数n，表示一共2^n个国家参赛。

第二行2^n个整数，第i个整数表示编号为i的国家的能力值(1≤i≤2^n)。

数据保证不存在平局。

输出

仅一个整数，表示亚军国家的编号。

样例组

输入
3
4 2 3 1 10 5 9 7
 
输出
1

---

题目思路

        这道题目在洛谷的二叉树题单中。但我不会手写二叉树，那该怎么办呢？既然二叉树这条路行不通，那似乎还可以借助STL库来解决这道题目。

        用红黑树还是priority_queue？都不是。我们可以借助vector和pair来解决这道题目。

        我们可以将利用pow()函数求出输入的总队伍数量，然后将其除2，写两个for循环，从而将读入分给两个vector数组a,b。

        读入程序如下：

void dr(vectorint,int> >a,vectorint,int> >b,int n)
{
    int x,m;
    cin>>n;
    x=pow(2,n)/2;//等价于x=pow(2,n-1);
	for(int i=1;i<=x;i++) cin>>m,a.push_back(make_pair(m,i));
	for(int i=1;i<=x;i++) cin>>m,b.push_back(make_pair(m,i+x));//注意后面应该for循环的i要加x
}

---

核心程序

          然后，我们对数组a进行sort()操作，数组b同样也进行sort()操作(核心程序)，然后就有两种可行做法：

        第一种做法是先将a,b进行reverse()操作，再比较a数组首位的实力值(first)和b数组首位的实力值(vector数组下标起始是0)。输出其中实力值较小的一个数的序号(.second)。

        时间复杂度O(n)。

        这样做的话，程序如下(程序多了一行reverse):

void sc(vector >a,vector >b)
{
    reverse(a.begin(),a.end());reverse(b.begin(),b.end());
	if(a[0].first>b[0].first) cout<<b[0].second;
	else cout<<a[0].second;
}

        第二种做法则是直接比较a,b的最后一位(倒数最后一名就是第一名)的实力值，然后输出其中实力值底的队伍的序号。

        时间复杂度O(1)。

        这样做的话，程序如下：

void sc(vectorint,int> >a,vectorint,int> >b)
{
    if(a[a.size()-1].first>b[b.size()-1].first) cout<size()-1].second;
	else cout<size()-1].second;
}

---

程序总结  

        那么总时间复杂度在O(n log n)和O(n*n)之间。考虑到2的7次方是128，而128的平方还不到两万(16384),那么这段程序是肯定可以过的。

        这样做可以得到两段程序。

        第一段程序如下：

#include
#define vp vector >
using namespace std;
vp a,b;int n,m,x;
int main()
{
	cin>>n;
    x=pow(2,n)/2;
	for(int i=1;i<=x;i++) 
        cin>>m,a.push_back(make_pair(m,i));
	for(int i=1;i<=x;i++) 
        cin>>m,b.push_back(make_pair(m,i+x));
	sort(a.begin(),a.end());sort(b.begin(),b.end());
	reverse(a.begin(),a.end());reverse(b.begin(),b.end());
	if(a[0].first>b[0].first) 
        cout<0].second;
	else cout<0].second;
	return 0;
}

        (第二段见下篇。）