P1309 瑞士轮澳门葡京手机网址 未到位 60

题材背景

在双人对决的竞赛性竞赛,如斯诺克、羽球、国际象棋中,最常见的比赛制度是淘汰赛和循环赛。前者的风味是竞赛场数少,每场都浮动刺激,但偶然性较高。后者的性状是相比公平,偶然性较低,但比赛进程往往格外冗长。

主旨中介绍的瑞士联邦轮比赛制度,因最早采纳于1895年在瑞士联邦开办的国际象棋竞技而得名。它能够用作是淘汰赛与循环赛的退让,既保障了较量的安居,又能使比赛日程不至于过长。

背景

在双人对决的比赛性比赛,如台球、羽球、国际象棋中,最普遍的比赛制度是淘汰赛和循环赛。前者的天性是比赛场数少,每场都浮动刺激,但偶然性较高。后者的特色是相比较公平,偶然性较低,但竞赛进度反复越发冗长。 
主旨中介绍的瑞士联邦轮比赛制度,因最早采纳于 1895
年在瑞士联邦开办的国际象棋竞赛而得名。

它能够作为是淘汰赛与循环赛的妥胁,既保险了竞赛的平静,又能使比赛日程不至于过长。

标题叙述

2*N 名编号为 1~2N 的运动员共进行揽胜轮竞技。每轮竞技开头前,以及独具竞赛甘休后,都会依据总分从高到低对运动员实行二回排行。选手的总分为首轮初始前的上马分数加桃月在场过的装有比赛的得分和。总分一样的,约确定人员编制号较小的运动员排行靠前。

每轮比赛的周旋安插与该轮比赛开端前的名次有关:第① 名和第三 名、第 3
名和第 4名、……、第②K – 1 名和第 2K名、…… 、第二N – 1
名和第贰N名,各举办一场较量。每场比赛胜者得1 分,负者得 0
分。也正是说除了首轮以外,其它轮竞赛的安排均不可能事先分明,而是要取决于选手在事先交锋中的表现。

现给定各样选手的启幕分数及其实力值,试计算在奥迪Q5 轮比赛过后,排行第 Q
的健儿编号是有些。大家只要选手的实力值两两分歧,且每场竞赛中实力值较高的总能获胜。

描述

2*N名编号为
1~2N的健儿共展开汉兰达轮竞技。每轮比赛开首前,以及独具比赛截止后,都会安份守己总分从高到低对选手进行一遍排名。选手的总分为率先轮初始前的初步分数加樱笋时到场过的装有比赛的得分和。总分一样的,约定编号较小的健儿名次靠前。 
每轮比赛的对峙安插与该轮比赛伊始前的排名有关:第壹 名和第二 名、第3名和第伍名、……、第1K-1名和第 2K名、…… 、第 2N-1
名和第贰N名,各实行一场竞赛。每场竞赛胜者得 1 分,负者得 0
分。也正是说除了首轮以外,别的轮交锋的布署均无法事先明显,而是要在于选手在事先交锋中的表现。 
现给定各样选手的发端分数及其实力值,试总计在 Lacrosse 轮比赛过后,排行第 Q
的选手编号是有点。我们借使选手的实力值两两分歧,且每场比赛后实力值较高的总能获胜。

输入输出格式

输入格式:

输入文件名为swiss.in 。

输入的首先行是四个正整数N、Wrangler 、Q,每三个数以内用2个空格隔开分离,表示有
2*N 名运动员、奥迪Q7 轮竞赛,以及我们关切的排行 Q。

其次行是2*N 个非负整数s1, s2, …, s2N,每八个数以内用贰个空格隔离,当中si 表示编号为i 的运动员的上马分数。 第1行是2*N 个正整数w1 , w2 , …,
w2N,每多个数以内用二个空格隔断,个中 wi 表示编号为i 的运动员的实力值。

输出格式:

输出文件名为swiss.out。

输出只有一行,包涵一个平头,即福睿斯 轮竞技甘休后,排行第 Q 的健儿的号码。

格式

输入输出样例

输入样例#1:

2 4 2 
7 6 6 7 
10 5 20 15 

出口样例#1:

1

输入格式

输入的第二行是四个正整数 N、RAV四 、Q,每三个数里面用七个空格隔开分离,表示有
2*N名选手、Odyssey 轮竞赛,以及大家关怀的排名 Q。 
其次行是 2*N个非负整数 s1, s2, …, s2N,每三个数以内用1个空格隔离,个中s 表示编号为 i 的健儿的先河分数。 
其三行是 2*N个正整数 w1, w2, …, w2N,每多个数里面用3个空格隔绝,在这之中 w
表示编号为 i 的健儿的实力值。

说明

【样例解释】

澳门葡京手机网址 1

【数据范围】

对于30% 的数据,1 ≤ N ≤ 100;

对于50% 的数据,1 ≤ N ≤ 10,000 ;

对于100%的数据,1 ≤ N ≤ 100,000,1 ≤ R ≤ 50,1 ≤ Q ≤ 2N,0 ≤ s1, s2, …,
s2N≤10^8,1 ≤w1, w2 , …, w2N≤ 10^8。

noip二零一二普及组第贰题。

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     int fenshu;
 9     int shili;
10     int bh;
11 }a[100001];
12 int n,r,q;
13 int comp(const node & a,const node & b)
14 {
15     if(a.fenshu!=b.fenshu)
16     return a.fenshu>b.fenshu;
17     else return a.bh<b.bh;
18 }
19 int main()
20 {
21     scanf("%d%d%d",&n,&r,&q);
22     n=n*2;
23     for(int i=1;i<=n;i++)
24         scanf("%d",&a[i].fenshu),a[i].bh=i;
25     for(int i=1;i<=n;i++)
26         scanf("%d",&a[i].shili);
27     sort(a+1,a+n+1,comp);
28     for(int j=1;j<=r;j++)
29     {
30         for(int i=1;i<=n;i=i+2)
31         {
32             
33             if(a[i].shili>=a[i+1].shili)
34             a[i].fenshu++;
35             else if(a[i].shili<a[i+1].shili)
36             a[i+1].fenshu++;
37         }
38         sort(a+1,a+n+1,comp);
39     }
40     printf("%d",a[q].bh);
41     
42     return 0;
43 }

 

输出格式

输出只有一行,包罗3个平头,即 中华V 轮竞技停止后,排行第 Q 的选手的编号。

样例1

样例输入1

2 4 2
7 6 6 7
10 5 20 15

样例输出1

1

限制

1s

提示

1 ≤ n ≤ 100,000
1 ≤ R ≤ 50
1 ≤ Q ≤ 2N
0 ≤ Si ≤ 10^8
1 ≤ Wi ≤ 10^8