Yao Lirong's Blog

P1309 瑞士轮

NOI
2019/05/30

题目来源：洛谷P1309 瑞士轮

  1. 胜者组和败者组分别是有序的，使用 mergesort 将两个有序同向数组进行归并（严格上来说不是归并排序），大大降低了时间复杂度 = O(n)。如果我们使用 quicksort，则默认整个数据是无序的，对每个数据都重新排序所以会超时
  2. 一种可以替代结构体的方法：排名的时候我们可以只对每个选手的序号进行排序，这样做既可以保证我们有各个人的排序，又可以保证他们的成绩和实力得到记录（序号对应着成绩和实力，在对序号根据实力排序的同时，每个序号对应的成绩和实力的顺序是不变的）
  3. sort 函数中 cmp 的使用方法
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int num,round,inquiry,score[200005],power[200005],No[200005],winner[100005],loser[100005];
///其中，No里每个下标代表选手的排名，power & score 的下标代表选手的序号
bool cmp(int, int);
void mergesort();
void compete();
int main()
{
    cin>>num>>round>>inquiry;
    for(int i=1;i<=2*num;i++) cin>>score[i];
    for(int i=1;i<=2*num;i++) cin>>power[i];
    for(int i=1;i<=2*num;i++) No[i]=i;

    //for(int i=1;i<=2*num;i++) cout<<No[i]<<" "<<score[i]<<endl;
    sort(No+1,No+1+2*num,cmp);
    //for(int i=1;i<=2*num;i++) cout<<No[i]<<" "<<score[i]<<endl;

    for(int i=1;i<=round;i++)
    {
        compete();
        mergesort();
    }

    cout<<No[inquiry];
    //while(true);
    return 0;

}
bool cmp(int m, int n)
{
    ///cmp函数使用范例
    if(score[m]==score[n]) return m<n;
    else return score[m]>score[n];
}

void compete()
{
    for(int i=1;i<=2*num;i=i+2)
    {
        if(power[No[i]]>power[No[i+1]])
        {
            score[No[i]]++;
            winner[i/2+1]=No[i];
            loser[i/2+1]=No[i+1];
        }
        else if(power[No[i]]<power[No[i+1]])
        {
            score[No[i+1]]++;
            winner[i/2+1]=No[i+1];
            loser[i/2+1]=No[i];
        }
    }
    /*cout<<"compete"<<endl;
    for(int i=1;i<=num;i++) cout<<winner[i]<<" "<<loser[i]<<endl;
    cout<<endl;*/
}

void mergesort()
{

    int i=1,j=1;
    while(i<=num && j<=num)
    {
        //if(score[winner[i]]>score[loser[j]])
        if(cmp(winner[i],loser[j])) ///完全无法理解这个地方只写一个cmp是怎么过的，难道不会有位于后面的相等score项实际比前面的相等score项序号更小这种情况吗
        {
            No[i+j-1]=winner[i];
            i++;
        }
        //else if(score[loser[j]]>score[winner[i]])
        else
        {
            No[i+j-1]=loser[j];
            j++;
        }
        /*else if(score[loser[j]]==score[winner[i]])
        {
            int k=0,temp[200005];
            while(score[winner[i]]==score[winner[i+1]]) temp[++k]=winner[i++];
            while(score[loser[j]]==score[loser[j]]) temp[++k]=loser[j++];
            sort(temp,temp+k);
            for(int a=1;a<=k;a++) No[a+i+j-1]=temp[a];
        }*/
    }

    while(i<=num)
    {
        No[i+num]=winner[i];
        i++;
    }
    while(j<=num)
    {
        No[j+num]=loser[j];
        j++;
    }

    /*cout<<"mergesort";
    for(int i=1;i<=num*2;i++) cout<<No[i]<<" ";
    cout<<endl;*/
}
/*
2 4 1
7 6 6 7
10 5 20 15
*/

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/P1309%20%E7%91%9E%E5%A3%AB%E8%BD%AE/

Publish date：May 30th 2019, 12:00:00 am

Update date：June 27th 2019, 8:26:56 pm

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book