【洛谷】P1309 瑞士轮

发表于 | 分类于

1. 题目描述

原题链接

2. 一开始的思路(会超时)

最直白的思路就是直接模拟，然后每次都进行一遍 sort。

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
#include <iostream>
#include <algorithm>
using namespace std;

//选手
struct Participant
{
    int index;
    int score;
    int ability;
};
//index, score, ability
Participant participants[200001];

//优先以分数降序排序，如果分数一样就按照编号排序
bool cmp(const Participant &p1, const Participant &p2)
{
    if (p1.score != p2.score)
        return p1.score > p2.score;
    else
        return p1.index < p2.index;
};

int main()
{
    ios::sync_with_stdio(false);
    int n, r, q;
    while (cin >> n >> r >> q)
    {
        //输入选手的初始得分和序号
        for (int i = 1; i <= 2 * n; ++i)
        {
            cin >> participants[i].score;
            participants[i].index = i;
        }
        //输入选手的能力值
        for (int i = 1; i <= 2 * n; ++i)
            cin >> participants[i].ability;
        //按照分数从大到小排序
        sort(participants + 1, participants + 2 * n + 1, cmp);
        //一共进行 R 轮比赛的模拟
        for (int i = 0; i < r; ++i)
        {
            //每相邻两人都比一次
            for (int j = 1; j < 2 * n; j += 2)
            {
                int winner = participants[j].ability > participants[j + 1].ability ? j : j + 1;
                //胜者得分
                participants[winner].score++;
            }
            //再调整排序
            sort(participants + 1, participants + 2 * n + 1, cmp);
        }
        cout << participants[q].index << endl;
    }
    return 0;
}

思路直白简单，但是会超时。

2. 分析一波

2.1 超时的原因

为啥会超时？这当然是废话了，题目规定了时间限制，超过了就是超过了呗。但是我们得反思一下，既然代码没有问题，是不是意味着还有更好的思路呢？

首先我们来想想，到底是哪里浪费的时间。显然当然是 sort 了！可为什么会浪费时间呢？我们注意到，在这个题目中 participants 无论在哪轮比赛后，都有一个特点，那就是它必然是交错有序的。换而言之，如果我们单独把胜者和败者分别拿出来然后按照原来的顺序排列起来，那这两个序列都是有序的。

明白了这一点，我们也就不难理解为什么 std::sort 表现不佳了。毕竟本来这个序列并没有那么无序，我们却非要用对待随机序列那样进行排序，当然会做很多无用的操作了！

2.2 使用 merge 改善算法

既然这样，我们就要思考一种更好的方法。看到两个有序的子序列，我们自然而然能联想到归并排序了（并不，我也是看了别人的解答才想到的）。如果我们把两个有序序列分开然后最后再合并起来，这不就大大提高效率了吗？

对时间复杂度进行简单的分析，原本的算法主体部分如下: 

1
2
3
4
5
6
7
8
sort;
for i = 1 : R with step = 1
{
    for (pair in participants)
        compete;
        modify score in participants;
    sort;
}

复杂度为 \(O(n\log{n}) + R\times (O(N) + O(n\log{n}))\)。

修改算法为: 

1
2
3
4
5
6
7
8
sort;
for i = 1 : R with step = 1
{
    for (pair in participants)
        compete;
        split to winners + losers;
    merge(winners, losers) to participants
}

复杂度为 \(O(n\log{n}) + R\times (O(N) + O(N))\)。

时间复杂度一下子降了好多！至于空间复杂度。。。谁在乎呢！

那么怎么 merge 呢？我们当然可以自己手写，不过最好的办法是直接用 std::merge，它就在 <algorithm> 头文件里。

1
2
3
4
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);

意思是：把 [first1, last1) 和 [first2, last2) 合并到 result 开头的空间里，最后一个参数是比较器。

3. AC 算法

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
#include <iostream>
#include <algorithm>
using namespace std;

struct Participant
{
    int index;
    int score;
    int ability;
};
//index, score, ability
Participant participants[200001];
Participant winners[100001];
Participant losers[100001];

bool cmp(const Participant &p1, const Participant &p2)
{
    if (p1.score != p2.score)
        return p1.score > p2.score;
    else
        return p1.index < p2.index;
};

int main()
{
    ios::sync_with_stdio(false);
    int n, r, q;
    while (cin >> n >> r >> q)
    {
        //输入选手的初始得分和序号
        for (int i = 1; i <= 2 * n; ++i)
        {
            cin >> participants[i].score;
            participants[i].index = i;
        }
        //输入选手的能力值
        for (int i = 1; i <= 2 * n; ++i)
            cin >> participants[i].ability;
        //按照分数从大到小排序
        sort(participants + 1, participants + 2 * n + 1, cmp);
        //R 轮比赛的模拟
        for (int i = 0; i < r; ++i)
        {
            //每相邻两人都比一次
            for (int j = 1; j < 2 * n; j += 2)
            {
                int winner = participants[j].ability > participants[j + 1].ability ? j : j + 1;
                int loser = participants[j].ability < participants[j + 1].ability ? j : j + 1;
                //分别把赢家和输家放入到不同的序列中
                //可以证明 winnders 和 losers 一定是有序的
                winners[(j + 1) / 2] = participants[winner];
                losers[(j + 1) / 2] = participants[loser];
                winners[(j + 1) / 2].score++;
            }
            //合并有序序列到 participants
            merge(
                winners + 1, winners + n + 1,
                losers + 1, losers + n + 1,
                participants + 1, cmp
            );
        }
        cout << participants[q].index << endl;
    }
    return 0;
}

4. 感言

以后不要看到排序就无脑 std::sort，对于这种可以划分为若干个有序序列的情况，用 ,erge 显然更加高效。