主题中介绍的瑞士联邦轮赛制,每轮交锋起头前

背景

在双人对决的竞赛性竞技,如斯诺克、羽球、国际象棋中,最广大的比赛制度是淘汰赛和循环赛。前者的特色是比赛场数少,每场都紧张激情,但偶然性较高。后者的表征是较为公平,偶然性异常的低,但竞技进度反复越发冗长。 
核心中牵线的瑞士联邦轮比赛制度,因最早选取于 1895年在瑞士设置的国际象棋比赛而得名。

它能够作为是淘汰赛与循环赛的妥协,既保险了较量的谐和,又能使比赛日程不至于过长。

难点背景

在双人对决的比赛性竞赛,如斯诺克、羽球、国际象棋中,最常见的比赛制度是淘汰赛和循环赛。前者的表征是竞比赛地方数少,每场都紧张激情,但偶然性较高。后者的性状是较为公平,偶然性相当低,但比赛进度往往十二分冗长。

大旨中牵线的瑞士轮比赛制度,因最早采纳于18九5年在瑞士办起的国际象棋比赛而得名。它能够看做是淘汰赛与循环赛的低头,既保险了比赛的安居,又能使比赛日程不至于过长。

描述

2*N名编号为
壹~二N的健儿共打开Odyssey轮竞技。每轮竞赛伊始前,以及有着竞赛甘休后,都会依据总分从高到低对运动员实行3次排行。选手的总分为第二轮起先前的发端分数加上已在场过的持有竞赛的得分和。总分同样的,约定编号相当小的健儿排行靠前。 
每轮竞赛的周旋布置与该轮竞技开首前的排行有关:第1 名和第一 名、第1名和第六名、……、第二K-一名和第 2K名、…… 、第 二N-1名和第二N名,各举行一场交锋。每场比赛胜者得 1 分,负者得 0
分。也正是说除了第三轮以外,此外轮交锋的配置均无法事先分明,而是要在于选手在前头交锋中的表现。 
现给定每个选手的起来分数及其实力值,试总括在 奥迪Q7 轮竞技过后,排行第 Q
的健儿编号是不怎么。大家若是选手的实力值两两区别,且每场竞技前实力值较高的总能获胜。

主题素材叙述

2*N 名编号为 1~2N 的运动员共开始展览索罗德轮比赛。每轮竞赛开端前,以及具备竞赛甘休后,都会遵照总分从高到低对运动员实行2次排行。选手的总分为第二轮开端前的始发分数加申月到位过的有所竞赛的得分和。总分一样的,约定编号比较小的运动员排名靠前。

每轮比赛的周旋安顿与该轮比赛开头前的排行有关:第二 名和第三 名、第 3名和第 四名、……、第一K – 一 名和第 2K名、…… 、第二N – 1名和第3N名,各实行一场竞技。每场比赛胜者得壹 分,负者得 0
分。也便是说除了首轮以外,别的轮较量的配备均不能事先明确,而是要取决于选手在头里交锋中的表现。

现给定各样选手的早先分数及其实力值,试总计在Tiggo 轮比赛过后,排行第 Q
的选手工编织号是稍稍。我们只要选手的实力值两两区别,且每场竞赛中实力值较高的总能胜球。

格式

输入输出格式

输入格式:

输入文件名叫swiss.in 。

输入的第壹行是四个正整数N、Enclave 、Q,每五个数里面用一个空格隔断,表示有
二*N 名运动员、帕杰罗 轮比赛,以及大家关怀的排名 Q。

第壹行是二*N 个非负整数s一, s2, …, s二N,每八个数里面用2个空格隔绝,当中si 表示编号为i 的健儿的上马分数。 第2行是贰*N 个正整数w壹 , w2 , …,
w贰N,每多少个数以内用三个空格隔绝,其中 wi 表示编号为i 的运动员的实力值。

输出格式:

出口文件名称为swiss.out。

输出唯有壹行,包罗2个平头,即陆风X8 轮竞技截至后,排行第 Q 的健儿的号码。

输入格式

输入的首先行是多少个正整数 N、猎豹CS6、Q,每多少个数以内用3个空格隔离,表示有
2*N名运动员、Sportage 轮竞技,以及大家关怀的排行 Q。 
其次行是 贰*N个非负整数 s1, s2, …, s二N,每四个数以内用二个空格隔离,其中s 表示编号为 i 的运动员的上马分数。 
其3行是 二*N个正整数 w一, w2, …, w贰N,每多个数里面用二个空格隔离,当中 w
表示编号为 i 的选手的实力值。

输入输出样例

输入样例#1:

2 4 2 
7 6 6 7 
10 5 20 15 

输出样例#1:

1

出口格式

出口唯有壹行,包括二个整数,即 汉兰达 轮比赛停止后,排行第 Q 的健儿的号子。

说明

【样例解释】

图片 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。

noip201一普遍组第二题。

 

 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 }

 

样例1

样例输入一

2 4 2
7 6 6 7
10 5 20 15

样例输出一

1

限制

1s

提示

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

相关文章