【深基16.例1】淘汰赛

题意

2^n 个国家按固定淘汰赛对阵，能力强者必胜。输出亚军编号。

思路

决赛一定由对阵表左半区最强者和右半区最强者参加，二者中较强的是冠军，较弱的就是亚军。因此无需逐轮模拟，只需分别取两半最大值，再取能力较小的决赛选手编号。

Python 知识

enumerate(scores,start=1) 同时得到国家编号和能力值。
max(...,key=lambda country:country[1]) 按元组的能力字段选半区冠军。
min(finalists,key=...) 再选较弱的决赛选手。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：key 函数指定比较依据。

代码

python

1
2
3
4
5
6
7
8
9n = int(input())
countries = list(enumerate(map(int, input().split()), start=1))
half = 1 << (n - 1)
finalists = (
    max(countries[:half], key=lambda country: country[1]),
    max(countries[half:], key=lambda country: country[1]),
)

print(min(finalists, key=lambda country: country[1])[0])

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
 * P4715 【深基16.例1】淘汰赛
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 260;

// 完全二叉树：tree[i] 存两个值
// [节点能力值, 该国原始编号]
pair<int,int> tree[MAXN * 2];
int n;

int main() {
    scanf("%d", &n);
    int total = 1 << n; // 选手总数 = 2^n
    // 读入叶子（第 1 轮选手）
    for (int i = total; i < 2 * total; ++i) {
        scanf("%d", &tree[i].first);
        tree[i].second = i - total + 1; // 原始编号
    }
    // 自底向上模拟淘汰赛
    for (int i = total - 1; i >= 1; --i) {
        int l = i * 2, r = i * 2 + 1;
        if (tree[l].first > tree[r].first) tree[i] = tree[l];
        else tree[i] = tree[r];
    }
    // 亚军 = 总决赛中输给冠军的一方
    if (tree[2].first > tree[3].first) printf("%d\n", tree[3].second);
    else printf("%d\n", tree[2].second);
    return 0;
}

Pythonic 写法

max/min + key：

python

1
2
3
4
5
6n = int(input())
countries = list(enumerate(map(int, input().split()), start=1))
half = 1 << (n - 1)
left = max(countries[:half], key=lambda x: x[1])
right = max(countries[half:], key=lambda x: x[1])
print(min(left, right, key=lambda x: x[1])[0])

复杂度

只扫描所有国家一次，时间复杂度 $O(2^n)$ ，保存选手为 $O(2^n)$ 。

总结

固定单败淘汰赛的亚军一定是决赛败者，而两个决赛选手分别是左右半区最大值。

【深基16.例1】淘汰赛

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结