P1309 瑞士轮

倚窗倾听风吹雨

[url=https://www.luogu.org/problemnew/show/P1309[/url]


题目背景
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。

本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长。

题目描述
2×N 名编号为 1-2N 的选手共进行R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1 名和第2 名、第 3 名和第 44名、……、第2K - 1 2K−1名和第 2K2K名、…… 、第2N - 1名和第2N名，各进行一场比赛。每场比赛胜者得1 分，负者得 0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值，试计算在R 轮比赛过后，排名第 Q 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

输入输出格式
输入格式：
第一行是三个正整数N,R,Q,每两个数之间用一个空格隔开，表示有2×N名选手、R 轮比赛，以及我们关心的名次 Q。

第二行是2×N 个非负整数s_1, s_2每两个数之间用一个空格隔开，其中 s_i 表示编号为i 的选手的初始分数。 第三行是2×N 个正整数w1 ,w2
​，每两个数之间用一个空格隔开，其中 wi 表示编号为i 的选手的实力值。

输出格式：
一个整数，即R 轮比赛结束后，排名第 Q 的选手的编号。

输入输出样例
输入样例#1：
2 4 2
7 6 6 7
10 5 20 15
输出样例#1：
1

倚窗倾听风吹雨

1. // luogu-judger-enable-o2
   
2. #include<iostream>
   
3. #include<algorithm>
   
4. using namespace std;
   
5. const int M=200010;
   
6. int n,q,r,winn,losen,alen;
   
7. struct node
   
8. {
   
9.     int s,num,v;
   
10. }p[M],win[M],lose[M];
    
11. bool cmp(node x,node y)
    
12. {
    
13.     if(x.s==y.s)return x.num<y.num;
    
14.     return x.s>y.s;
    
15. }
    
16. void merge()
    
17. {
    
18.     int i=1,j=1;
    
19.     alen=0;
    
20.     while(i<=winn && j<=losen)
    
21.     {
    
22.         if(cmp(win[i],lose[j]))
    
23.         {
    
24.             p[++alen].s=win[i].s;
    
25.             p[alen].num=win[i].num;
    
26.             p[alen].v=win[i++].v;
    
27.         }
    
28.         else
    
29.         {
    
30.             p[++alen].s=lose[j].s;
    
31.             p[alen].num=lose[j].num;
    
32.             p[alen].v=lose[j++].v;
    
33.         }
    
34.     }
    
35.     while(i<=winn)
    
36.     {
    
37.         p[++alen].s=win[i].s;
    
38.         p[alen].num=win[i].num;
    
39.         p[alen].v=win[i++].v;
    
40.     }
    
41.     while(j<=losen)
    
42.     {
    
43.         p[++alen].s=lose[j].s;
    
44.         p[alen].num=lose[j].num;
    
45.         p[alen].v=lose[j++].v;
    
46.     }
    
47. }
    
48. int main()
    
49. {
    
50.     cin>>n>>r>>q;
    
51.     for(int i=1;i<=n+n;i++)
    
52.         cin>>p[i].s;
    
53.     for(int i=1;i<=n+n;i++)
    
54.     {
    
55.         cin>>p[i].v;
    
56.         p[i].num=i;
    
57.     }
    
58.     sort(p+1,p+n+n+1,cmp);
    
59.     for(int i=1;i<=r;i++)
    
60.     {
    
61.         winn=0;losen=0;
    
62.         for(int j=1;j<=n+n-1;j+=2)
    
63.         {
    
64.             if(p[j].v>p[j+1].v)
    
65.             {
    
66.                 p[j].s++;
    
67.                 win[++winn].s=p[j].s;
    
68.                 win[winn].num=p[j].num;
    
69.                 win[winn].v=p[j].v;
    
70.                 lose[++losen].s=p[j+1].s;
    
71.                 lose[losen].num=p[j+1].num;
    
72.                 lose[losen].v=p[j+1].v;
    
73.             }
    
74.             else
    
75.             {
    
76.                 p[j+1].s++;
    
77.                 win[++winn].s=p[j+1].s;
    
78.                 win[winn].num=p[j+1].num;
    
79.                 win[winn].v=p[j+1].v;
    
80.                 lose[++losen].s=p[j].s;
    
81.                 lose[losen].num=p[j].num;
    
82.                 lose[losen].v=p[j].v;
    
83.             }
    
84.         }
    
85.         merge();
    
86.         /*for(int j=1;j<=n+n;j++)
    
87.         cout<<p[j].s<<" "<<p[j].num<<endl;
    
88.         cout<<endl;*/
    
89.     }
    
90.     cout<<p[q].num<<endl;
    
91.     return 0;
    
92. }
    

复制代码

universehyf

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. struct stu{int s,w,ran;}st[220000],win[120000],lose[120000];
   
5. int n,r,q,i,j,ii,jj;
   
6. bool mycomp(stu x,stu y)
   
7. {
   
8.     return (x.s==y.s)?(x.ran<y.ran):(x.s>y.s);
   
9. }
   
10. int main()
    
11. {
    
12.     cin>>n>>r>>q;
    
13.     for(i=1;i<=2*n;i++) cin>>st[i].s;
    
14.     for(i=1;i<=2*n;i++) cin>>st[i].w;
    
15.     for(i=1;i<=2*n;i++) st[i].ran=i;
    
16.     sort(st+1,st+1+2*n,mycomp);
    
17.   ///  for(i=1;i<=2*n;i++)cout<<st[i].ran<<" ";
    
18.     for(i=1;i<=r;i++)
    
19.     {
    
20.         ii=0;jj=0;
    
21.         for(j=1;j<=2*n;j+=2)
    
22.         {
    
23.             if(st[j].w<st[j+1].w)
    
24.             {
    
25.                 st[j+1].s++;
    
26.                 win[++ii].s=st[j+1].s;
    
27.                 win[ii].w=st[j+1].w;
    
28.                 win[ii].ran=st[j+1].ran;
    
29.                 lose[++jj].s=st[j].s;
    
30.                 lose[jj].w=st[j].w;
    
31.                 lose[jj].ran=st[j].ran;
    
32.             }
    
33.             else
    
34.             {
    
35.                 st[j].s++;
    
36.                 win[++ii].s=st[j].s;
    
37.                 win[ii].w=st[j].w;
    
38.                 win[ii].ran=st[j].ran;
    
39.                 lose[++jj].s=st[j+1].s;
    
40.                 lose[jj].w=st[j+1].w;
    
41.                 lose[jj].ran=st[j+1].ran;
    
42.             }
    
43.         }
    
44.         int lo=1,wi=1,k=1;
    
45.         while(lo<=n&&wi<=n)
    
46.         {
    
47.             if(mycomp(win[wi],lose[lo]))
    
48.             {
    
49.                 st[k].s=win[wi].s;
    
50.                 st[k].w=win[wi].w;
    
51.                 st[k].ran=win[wi].ran;
    
52.                 k++;wi++;
    
53.             }
    
54.             else
    
55.             {
    
56.                 st[k].s=lose[lo].s;
    
57.                 st[k].w=lose[lo].w;
    
58.                 st[k].ran=lose[lo].ran;
    
59.                 k++;lo++;
    
60.             }
    
61.         }
    
62.         while(wi<=n)
    
63.         {
    
64.             st[k].s=win[wi].s;
    
65.             st[k].w=win[wi].w;
    
66.             st[k].ran=win[wi].ran;
    
67.             k++;wi++;
    
68.         }
    
69.         while(lo<=n)
    
70.         {
    
71.             st[k].s=lose[lo].s;
    
72.             st[k].w=lose[lo].w;
    
73.             st[k].ran=lose[lo].ran;
    
74.             k++;lo++;
    
75.         }/*
    
76.         for(int o=1;o<=n+n;o++)
    
77.         cout<<st[o].s<<" "<<st[o].ran<<endl;
    
78.         cout<<endl;*/
    
79.     }
    
80.     cout<<st[q].ran;
    
81.     return 0;
    
82. }

复制代码