当前位置：首页 > news >正文

题解：AtCoder AT_awc0085_a Tournament Elimination Round

news 2026/6/8 1:34:34

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：A - Tournament Elimination Round (atcoder.jp)

【题目描述】

A single-elimination tournament is held withN NNplayers. Here,N NNis a power of2 22.

Each player is assigned a number from1 11toN NN, and the strength of playeri iiisS i S_iSi. All players have distinct strengths, and in any match, the player with the greater strength value always wins. A player who loses is eliminated from the tournament, and matches continue until a single champion is determined.

SinceN NNis a power of2 22, the tournament consists of exactlyR = log ⁡ 2 N R = \log_2 NR=log2Nrounds. The matchups for each round are determined as follows:

Round1 11:Player2 i − 1 2i-12i−1and player2 i 2i2iplay against each other. This is called matchi iiof round1 11(i = 1 , 2 , … , N / 2 i = 1, 2, \ldots, N/2i=1,2,…,N/2).
Roundr rr(r ≥ 2 r \geq 2r≥2):The winner of match2 j − 1 2j-12j−1and the winner of match2 j 2j2jfrom the previous round (roundr − 1 r-1r−1) play against each other. This is called matchj jjof roundr rr(j = 1 , 2 , … , N / 2 r j = 1, 2, \ldots, N/2^rj=1,2,…,N/2r).

Match numbers within each round are numbered starting from1 11and are reassigned for each round. In roundR RR, there is only one match, and its winner is the champion.

For each player, determine the round number in which that player is defeated. However, since the champion is never defeated, output0 00for the champion. Rounds are numbered starting from1 11.

一场单败淘汰赛有N NN名选手参加。这里，N NN是2 22的幂。

每位选手被分配一个从1 11到N NN的编号，选手i ii的强度为S i S_iSi。所有选手的强度互不相同，在任何一场比赛中，强度值更大的选手总是获胜。输掉比赛的选手被淘汰出局，比赛继续直到决出唯一的冠军。

由于N NN是2 22的幂，比赛恰好有R = log ⁡ 2 N R = \log_2 NR=log2N轮。每一轮的对阵安排如下：

第1 11轮：选手2 i − 1 2i-12i−1和选手2 i 2i2i相互对战。这被称为第1 11轮的第i ii场比赛（i = 1 , 2 , … , N / 2 i = 1, 2, \ldots, N/2i=1,2,…,N/2）。
第r rr轮（r ≥ 2 r \geq 2r≥2）：上一轮（第r − 1 r-1r−1轮）第2 j − 1 2j-12j−1场比赛的胜者和第2 j 2j2j场比赛的胜者相互对战。这被称为第r rr轮的第j jj场比赛（j = 1 , 2 , … , N / 2 r j = 1, 2, \ldots, N/2^rj=1,2,…,N/2r）。

每轮内部的比赛编号从1 11开始，并且每轮重新编号。在第R RR轮，只有一场比赛，其胜者即为冠军。

对于每位选手，确定该选手在哪一轮被淘汰。但是，由于冠军从未被淘汰，为冠军输出0 00。轮次编号从1 11开始。

【输入】

N NN
S 1 S_1S1S 2 S_2S2… \ldots…S N S_NSN

The first line gives the number of playersN NN.

The second line gives the strengthsS 1 , S 2 , … , S N S_1, S_2, \ldots, S_NS1,S2,…,SNof each player, separated by spaces.

【输出】

OutputN NNintegers separated by spaces on a single line. Thei ii-th value is the round number in which playeri iiis defeated. For the champion, output0 00.

【输入样例】

4 1 4 3 2

【输出样例】

1 0 2 1

【算法标签】

#模拟

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=530005;// 定义最大数组长度intn;// 选手数量structNode{intid,s;// 选手编号id，选手实力s}a[N],b[N];// 当前轮数组a，下一轮数组bintrd[N];// 记录每个选手被淘汰的轮数intmain()// 主函数{cin>>n;// 输入选手数量for(inti=1;i<=n;i++)// 初始化所有选手{a[i].id=i;// 设置选手编号cin>>a[i].s;// 输入选手实力}intcur1=n;// 当前轮参赛选手数量intcnt=0;// 当前轮数计数器while(true)// 模拟淘汰赛{cnt++;// 轮数加1intcur2=0;// 下一轮选手数量for(inti=1;i<=cur1;i+=2)// 两两比较{if(a[i].s>a[i+1].s)// 如果左边选手更强{cur2++;// 下一轮选手数量加1b[cur2].id=a[i].id,b[cur2].s=a[i].s;// 左边选手晋级rd[a[i+1].id]=cnt;// 右边选手被淘汰}else// 如果右边选手更强{cur2++;// 下一轮选手数量加1b[cur2].id=a[i+1].id,b[cur2].s=a[i+1].s;// 右边选手晋级rd[a[i].id]=cnt;// 左边选手被淘汰}}cur1=cur2;// 更新当前轮选手数量memcpy(a,b,sizeof(b));// 将下一轮数据复制到当前轮if(cur2==1)break;// 如果只剩1名选手，比赛结束}for(inti=1;i<=n;i++)// 输出结果cout<<rd[i]<<" ";// 输出每个选手被淘汰的轮数cout<<endl;// 换行return0;// 程序正常结束}