【C++】【题解】淘汰赛 二叉树 P4715

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

输入格式

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

第二行 2^n2n 个整数，第 ii 个整数表示编号为 ii 的国家的能力值（1\leq i \leq 2^n1≤i≤2n）。

数据保证不存在平局。

输出格式

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

输入输出样例

输入 #1复制

3
4 2 3 1 10 5 9 7

输出 #1复制

1

方法一

方法一用了二叉树的思想，最后错了两个测试点得了60分。改进写了一下n=1的情况，还是错了一个测试点，得了80分。（写题解的时候才发现一个bug，最后改了就AC了）

后来看题解看到了一个很好的思路，就是方法二。最后方法二也AC通过了。

不过方法二的思路比较简单，所以我两个题解都复盘一下。

#include <bits/stdc++.h>
#include <algorithm>
//头文件无特殊
using namespace std;
int main()
{int n;cin >> n;int num = pow(2,n);
//备用2的n次方的数值，后面看起来清爽一点int arr[num];
//定义初始数据 int list[n+1][num];
//用二维数组定义二叉树，最复杂分支为第0行，依次向下 for(int i = 0 ; i < num ; i++){cin >> arr[i];list[0][i] = arr[i];}if(n == 1)
{if(arr[0] < arr[1]){cout << n;}else{cout << n+1;}return 0;
}
//后来debug的时候发现当n=1的时候
//这种做法arr和list会存在冲突 
//所以需要提前判断一下n=1的情况int now = 0;int lin = 0;for(int i = 0 ; i < n ; i++){for(int j = 0 ; j < num ; j+=2){list[i+1][now] = max(list[i][j],list[i][j+1]);now++;}now = 0;num/=2;//每次分支队伍数量减半，实测可以防止数组爆炸 lin++;//储存list的行数，下一行代码要用 }int ans = min(list[lin-1][0],list[lin-1][1]);//将list的lin-1行的两个数据进行比较//lin为最后一行仅剩冠军，所以lin-1行 为决赛，取数值较小的就是answer for(int i = 0 ; i < pow(2,n) ; i++){if(arr[i] == ans){cout << i+1;}} 
//因为给的数据具有唯一性，所以遍历find一下序号输出即可 return 0;
}

方法二

题解给了灵感。

这道题和世界杯淘汰赛是一样的，可以看到所有队伍分为左右两大块。

阿根廷和法国各是两边的最强的队伍，所以冠军就是两边中最强的两支队伍的优胜者，反之就是亚军。

因为这道题是有数值代表绝对实力的，所以可以在两边冒泡排一下最大的数字，然后用min比一下最终的两个数，较小的就是答案。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main()
{int n;cin >> n;int num = pow(2,n);int arr[num];int temp1 = 0;int temp2 = 0;for(int i = 0 ; i < num ; i++){cin >> arr[i];}for(int i = 0 ; i < num / 2 ; i++){if(arr[i] > temp1){temp1 = arr[i];}}for(int i = num / 2 ; i < num ; i++){if(arr[i] > temp2){temp2 = arr[i];}}
//两边分别查找出最大数 for(int i = 0 ; i < num ; i++){if(arr[i] == min(temp1,temp2)){cout << i+1;return 0;}}
//最终min对比一下，再遍历输出序号 return 0;
}