[NOIP 2011 普及组] 瑞士轮

题意

有 2n 个选手，每个人有：

当前分数
实力值

每一轮按当前排名两两配对：

第 1 和第 2
第 3 和第 4
…

实力值更高的人必胜，并且分数加 1。

每轮结束后重新按：

分数从大到小
若分数相同，编号小的在前

重新排名。

问 r 轮之后，第 q 名是谁。

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

struct Player {
    int id;
    int score;
    int power;
};

bool better(Player x, Player y) {
    if (x.score != y.score) {
        return x.score > y.score;
    }
    return x.id < y.id;
}

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

    int n, r, q;
    cin >> n >> r >> q;

    vector<Player> a(2 * n + 1);
    for (int i = 1; i <= 2 * n; i++) {
        a[i].id = i;
        cin >> a[i].score;
    }
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i].power;
    }

    sort(a.begin() + 1, a.end(), better);

    // brute.cpp：每轮都直接模拟比赛，再整体排序。
    while (r--) {
        for (int i = 1; i <= 2 * n; i += 2) {
            if (a[i].power > a[i + 1].power) {
                a[i].score++;
            }
            else {
                a[i + 1].score++;
            }
        }
        sort(a.begin() + 1, a.end(), better);
    }

    cout << a[q].id << '\n';
    return 0;
}

朴素做法是每一轮：

按当前排名两两比赛
更新分数
再把所有人整体排序

这样一轮是 $O(n log n)$ ，总复杂度是 $O(r n log n)$ 。虽然这题 r 只有 50，但 n 可到 10^5，还能继续优化。

关键观察是：

每一轮比赛前，整个序列本来就是按排名有序的
每两个相邻选手比完以后，胜者的分数加 1，败者分数不变

把所有胜者按比赛顺序取出来，会发现他们之间仍然有序；同理，所有败者之间也仍然有序。

原因是原序列本来有序，而每个胜者只是比原来多了 1 分，败者分数不变，所以不会破坏各自组内的相对有序性。

于是每一轮做完以后，不需要再对全部 2n 个人重新 sort，只需要：

顺次得到胜者组
顺次得到败者组
把两个有序序列线性归并

这样每一轮就能做到 $O(n)$ ，总复杂度降到 $O(rn)$ 。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

struct Player {
    int id;
    int score;
    int power;
};

int n, r, q;
Player a[MAXN];
Player win_group[MAXN];
Player lose_group[MAXN];
Player merged[MAXN];

bool better(Player x, Player y) {
    if (x.score != y.score) {
        return x.score > y.score;
    }
    return x.id < y.id;
}

void merge_groups() {
    int i = 1;
    int j = 1;
    int k = 1;

    while (i <= n && j <= n) {
        if (better(win_group[i], lose_group[j])) {
            merged[k++] = win_group[i++];
        }
        else {
            merged[k++] = lose_group[j++];
        }
    }

    while (i <= n) {
        merged[k++] = win_group[i++];
    }
    while (j <= n) {
        merged[k++] = lose_group[j++];
    }

    for (int t = 1; t <= 2 * n; t++) {
        a[t] = merged[t];
    }
}

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

    cin >> n >> r >> q;
    for (int i = 1; i <= 2 * n; i++) {
        a[i].id = i;
        cin >> a[i].score;
    }
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i].power;
    }

    sort(a + 1, a + 2 * n + 1, better);

    while (r--) {
        int win_cnt = 0;
        int lose_cnt = 0;

        for (int i = 1; i <= 2 * n; i += 2) {
            Player x = a[i];
            Player y = a[i + 1];

            if (x.power > y.power) {
                x.score++;
                win_group[++win_cnt] = x;
                lose_group[++lose_cnt] = y;
            }
            else {
                y.score++;
                win_group[++win_cnt] = y;
                lose_group[++lose_cnt] = x;
            }
        }

        merge_groups();
    }

    cout << a[q].id << '\n';
    return 0;
}

复杂度

初始排序： $O(n log n)$
每轮比赛 + 归并： $O(n)$

总时间复杂度： $O(n log n + rn)$ ，空间复杂度： $O(n)$ 。

总结

这题最重要的不是“模拟比赛”，而是看出：

胜者组有序
败者组有序
所以新排名可以靠一次归并得到

本质上是“模拟 + 归并”的题，而不是每轮都重新全排序。

[NOIP 2011 普及组] 瑞士轮

目录

题意

思路

代码

复杂度

总结