写在前面
这是本蒟蒻的第三篇题解。由于作者水平不高,本题解存在有数量庞大的错误。对于题解中的错误、可优化部分,欢迎各位大佬批评指正!不合适的部分,还请多多包涵!
本题目来源于洛谷。网址https://www.luogu.com.cn/problem/P4715。
本博客非营利性,如遇侵权,请联系作者删除,谢谢!
题面
【深基16.例1】淘汰赛
题目描述
有 \(2^n\)(\(n\le7\))个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值,且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛,胜者晋级。3 号国家和 4 号国家也踢一场,胜者晋级……晋级后的国家用相同的方法继续完成赛程,直到决出冠军。给出各个国家的能力值,请问亚军是哪个国家?
输入格式
第一行一个整数 \(n\),表示一共 \(2^n\) 个国家参赛。
第二行 \(2^n\) 个整数,第 \(i\) 个整数表示编号为 \(i\) 的国家的能力值(\(1\leq i \leq 2^n\))。
数据保证不存在平局。
输出格式
仅一个整数,表示亚军国家的编号。
样例 #1
样例输入 #1
3
4 2 3 1 10 5 9 7
样例输出 #1
1
题目解释
这道题无非就是用找最终晋级决赛的两队中能力较弱的一支,纯纯的模拟题……
但是!
他挖了个坑……
你以为排序完找第二大的就完事了?远没有你想的那么简单!
事实上,如果排名第二的队伍很不幸与第一(最后的冠军)在决赛前相遇,根据题意,第一会打败第二,第二也无法晋级决赛。因此,亚军不一定就是能力第二名。这句话有点费脑子,还请消化理解一下……
只要意识到这一点,整道题立马就迎刃而解了:我们用两个二叉树分别存储国家编号和能力,然后输出第二层能力较小者的编号,完毕。
等等,为什么是两个二叉树,找一个存储编号?一般编号不是直接用下标的吗?
由于一开始是初赛,因此两个二叉树只有叶子结点能存入初始数据……有点麻烦,要不,再理解理解?
理解完了?好,咱们进入下一步!
代码实现
前期准备
(不用解释了吧)
int a[260],No[260];//分别存储能力和编号
int n;
搜索进行时
void dfs(int x)//x作下标
{
if(x>=1<<n)//"1<<n"表示2^n
{
return;//遍历完全部,结束
}
dfs(2*x);//遍历左子树
dfs(2*x+1);//遍历右子树
if(a[2*x]>a[2*x+1])//如果左侧胜利
{
a[x]=a[2*x];//胜利方编号、能力为左侧
No[x]=No[2*x];
}
else//右侧胜利亦然
{
a[x]=a[2*x+1];
No[x]=No[2*x+1];
}
}
被迫工作的主函数
int main()
{
cin>>n;
for(int i=0;i<1<<n;i++)
{
cin>>a[i+(1<<n)];//输入能力值
No[i+(1<<n)]=i+1; //由于i由0启用,而题目编号由1启用,故需+1
}
dfs(1);
if(a[2]>a[3])//左侧为冠军
cout<<No[3];//输出右侧的亚军
else//反之亦然
cout<<No[2];
return 0;
}
完整代码
#include<bits/stdc++.h>
using namespace std;
int a[260],No[260];
int n;
void dfs(int x)
{
if(x>=1<<n)
{
return;
}
dfs(2*x);
dfs(2*x+1);
if(a[2*x]>a[2*x+1])
{
a[x]=a[2*x];
No[x]=No[2*x];
}
else
{
a[x]=a[2*x+1];
No[x]=No[2*x+1];
}
}
int main()
{
cin>>n;
for(int i=0;i<1<<n;i++)
{
cin>>a[i+(1<<n)];
No[i+(1<<n)]=i+1;
}
dfs(1);
if(a[2]>a[3])
cout<<No[3];
else
cout<<No[2];
return 0;
}
请注意
- 题目数据最大值就到\(2^8\),因此数组到260就绝对没有问题
- 用不惯左移,用
pow(2,n)
也是可以的,只是效率会明显比作为位运算的左移低 - 二叉树中的公式:第x个结点,其左结点为2x,右结点为2x+1
(话说这个都不知道大概也用不了二叉树) - 主函数内存编号的
i+1
在“代码实现”中已经讲了,可以再看一下
时间复杂度
题目最大n值为\(8\),在此值下,总循环次数估计值为\(512\)(\(2^9\))。很明显,通过绝对没有问题。
以下为洛谷运行结果:
写在最后
这次的题解花了1小时,越来越快了 <( ̄︶ ̄)> !不知质量有没有下降?
再次表示:
这是本蒟蒻的第二篇题解。由于作者水平不高,本题解存在有数量庞大的错误。对于题解中的错误、可优化部分,欢迎各位大佬批评指正!不合适的部分,还请多多包涵!
本题目来源于洛谷。网址https://www.luogu.com.cn/problem/P4715。
本博客非营利性,如遇侵权,请联系作者删除,谢谢!
最后,都看到这里了,不推荐一个再走吗?