瑞士轮

题目描述

$2N$ 名编号 $1\sim 2N$ 的选手进行 $R$ 轮瑞士轮：每轮开始前按总分（初始分加已得分数，同分编号小者靠前）排名，第 $2k-1$ 名与第 $2k$ 名比赛，实力高者获胜并得 1 分；求 $R$ 轮结束后第 $Q$ 名的选手编号。

输入第一行 $N,R,Q$ ，第二行 $2N$ 个初始分数 $s_i$ ，第三行 $2N$ 个实力值 $w_i$ ；输出一个整数，即第 $Q$ 名选手的编号。数据范围 $1\le N\le10^5$ ， $1\le R\le50$ ， $1\le Q\le 2N$ ， $0\le s_i\le10^8$ ， $w_i$ 两两不同。样例输入三行 2 4 2、7 6 6 7、10 5 20 15，输出 1。

思路

朴素做法每轮整体排序是 $O(RN\log N)$ 。注意到每轮胜者分数同时加 1、负者分数不变，因此按赛前名次列出的胜者组和负者组各自仍有序，新一轮排名只需把这两个有序表归并一次，总复杂度降到 $O(N\log N+RN)$ 。

参考代码

Python 版：

python

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def play_round(order: list[int], score: list[int], power: list[int]) -> list[int]:
    """打完一轮并返回新排名：胜者组、负者组各自仍有序，归并即可。"""
    winners: list[int] = []
    losers: list[int] = []
    for k in range(0, len(order), 2):
        a, b = order[k], order[k + 1]
        w, l = (a, b) if power[a] > power[b] else (b, a)
        score[w] += 1  # 胜者加一分
        winners.append(w)
        losers.append(l)

    merged: list[int] = []
    i = j = 0
    while i < len(winners) and j < len(losers):
        a, b = winners[i], losers[j]
        # a 排在 b 前 ⟺ 分数更高，或同分且编号更小
        ahead = score[a] > score[b] or (score[a] == score[b] and a < b)
        if ahead:
            merged.append(a)
            i += 1
        else:
            merged.append(b)
            j += 1
    return merged + (winners[i:] or losers[j:])


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, r, q = next(data), next(data), next(data)
    m = 2 * n
    score = [next(data) for _ in range(m)]
    power = [next(data) for _ in range(m)]

    # 初始排名：总分从高到低，同分编号小的在前
    order = sorted(range(m), key=lambda i: (-score[i], i))
    for _ in range(r):
        order = play_round(order, score, power)

    print(order[q - 1] + 1)  # 选手编号从 1 开始


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:34
 * update_at: 2026-10-06 14:34
 */
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXM = 200005; // 选手数 2N 的上界，N <= 100000

ll n, r, q;            // 每边人数、轮数、询问名次
ll m;                  // 选手总数 2N
ll score[MAXM];        // score[i] 表示第 i 号选手当前总分（1-indexed）
ll power[MAXM];        // power[i] 表示第 i 号选手的实力值
ll order[MAXM];        // order[k] 表示当前第 k 名的选手编号
ll winner[MAXM];       // 本轮胜者组：按本轮赛前名次排列
ll loser[MAXM];        // 本轮负者组：与胜者组一一对应
ll nxt[MAXM];          // 归并两个有序组后的新排名

// 排名关键字：(总分降序，同分编号升序)
bool cmp_rank(ll a, ll b) {
    if (score[a] != score[b]) {
        return score[a] > score[b];
    }
    return a < b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> r >> q;
    m = 2 * n;
    for (ll i = 1; i <= m; i++) {
        cin >> score[i];
    }
    for (ll i = 1; i <= m; i++) {
        cin >> power[i];
    }

    for (ll i = 1; i <= m; i++) {
        order[i] = i;
    }
    sort(order + 1, order + m + 1, cmp_rank);

    for (ll rd = 1; rd <= r; rd++) {
        // 每轮按当前排名两两配对，实力高者获胜并加一分
        ll win_cnt = 0;
        ll lose_cnt = 0;
        for (ll k = 1; k <= m; k += 2) {
            ll a = order[k];
            ll b = order[k + 1];
            if (power[a] > power[b]) {
                score[a]++;
                winner[++win_cnt] = a;
                loser[++lose_cnt] = b;
            } else {
                score[b]++;
                winner[++win_cnt] = b;
                loser[++lose_cnt] = a;
            }
        }

        // 胜者组内部同时加一分、负者组内部不变，两组各自仍有序，归并即可
        ll i = 1;
        ll j = 1;
        ll idx = 0;
        while (i <= win_cnt && j <= lose_cnt) {
            if (cmp_rank(winner[i], loser[j])) {
                nxt[++idx] = winner[i++];
            } else {
                nxt[++idx] = loser[j++];
            }
        }
        while (i <= win_cnt) {
            nxt[++idx] = winner[i++];
        }
        while (j <= lose_cnt) {
            nxt[++idx] = loser[j++];
        }
        for (ll k = 1; k <= m; k++) {
            order[k] = nxt[k];
        }
    }

    cout << order[q] << '\n';
    return 0;
}

目录

题目描述

思路

参考代码