P1309 瑞士联邦轮 未到位 60葡京娱乐软件下载

题材背景

在双人对决的比赛性比赛,如斯诺克、羽毛球、国际象棋中,最广大的比赛制度是淘汰赛和循环赛。前者的风味是竞赛场数少,每场都紧张刺激,但偶然性较高。后者的性状是较为公平,偶然性较低,但比赛进度反复尤其冗长。

宗旨中介绍的瑞士联邦轮比赛制度,因最早采取于1895年在瑞士联邦设置的国际象棋比赛而得名。它能够当做是淘汰赛与循环赛的妥胁,既保障了竞赛的安居乐业,又能使比赛日程不至于过长。

背景

在双人对决的竞赛性比赛,如台球、羽球、国际象棋中,最广泛的比赛制度是淘汰赛和循环赛。前者的特色是竞赛场数少,每场都浮动刺激,但偶然性较高。后者的风味是较为公平,偶然性较低,但竞赛进程反复十三分冗长。 
核心中介绍的瑞士联邦轮比赛制度,因最早接纳于 1895
年在瑞士联邦设置的国际象棋竞技而得名。

它能够看做是淘汰赛与循环赛的妥协,既保证了较量的安定团结,又能使比赛日程不至于过长。

难点叙述

2*N 名编号为 1~2N 的健儿共展开PRADO轮竞技。每轮竞赛发轫前,以及具有比赛截止后,都会依据总分从高到低对运动员实行一回排行。选手的总分为第一批次开头前的开端分数加晚春参预过的持有竞赛的得分和。总分一样的,约定编号较小的健儿排行靠前。

每轮竞技的对峙布署与该轮比赛先导前的排名有关:第① 名和第一 名、第 3
名和第 4名、……、第壹K – 1 名和第 2K名、…… 、第3N – 1
名和第壹N名,各实行一场较量。每场比赛胜者得1 分,负者得 0
分。也便是说除了第一轮以外,别的轮交锋的布置均不可能事先分明,而是要取决于选手在前头交锋中的表现。

现给定每一种选手的发端分数及其实力值,试总括在奥迪Q7 轮竞赛过后,排行第 Q
的健儿编号是稍微。大家要是选手的实力值两两差别,且每场竞技前实力值较高的总能胜球。

描述

2*N名编号为
1~2N的选手共开始展览牧马人轮竞技。每轮比赛起头前,以及拥有竞赛结束后,都会遵循总分从高到低对选手进行二遍排行。选手的总分为率先轮开头前的初阶分数加淑节插足过的有着竞技的得分和。总分一样的,约确定人员编制号较小的健儿排名靠前。 
每轮比赛的对抗布署与该轮竞赛最先前的排名有关:第二 名和第1 名、第1名和第6名、……、第叁K-1名和第 2K名、…… 、第 2N-1
名和第①N名,各举办一场较量。每场比赛胜者得 1 分,负者得 0
分。也便是说除了第一批次以外,其余轮竞技的安顿均不能够事先明确,而是要取决于选手在此前交锋中的表现。 
现给定每种选手的起始分数及其实力值,试总计在 奥迪Q3 轮竞赛过后,排名第 Q
的运动员编号是有个别。大家只要选手的实力值两两区别,且每场竞赛后实力值较高的总能赢球。

输入输出格式

输入格式:

输入文件名为swiss.in 。

输入的率先行是四个正整数N、Wrangler 、Q,每四个数以内用贰个空格隔绝,表示有
2*N 名选手、途乐 轮竞技,以及我们关怀的排行 Q。

第一行是2*N 个非负整数s1, s2, …, s2N,每三个数里面用2个空格隔绝,其中si 表示编号为i 的选手的开始分数。 第2行是2*N 个正整数w1 , w2 , …,
w2N,每多少个数里面用1个空格隔开分离,个中 wi 表示编号为i 的选手的实力值。

输出格式:

出口文件名为swiss.out。

输出唯有一行,包蕴二个整数,即CRUISER 轮比赛结束后,排行第 Q 的运动员的数码。

格式

输入输出样例

输入样例#1:

2 4 2 
7 6 6 7 
10 5 20 15 

输出样例#1:

1

输入格式

输入的首先行是八个正整数 N、Haval、Q,每七个数以内用贰个空格隔离,表示有
2*N名运动员、PRADO 轮比赛,以及大家关注的排行 Q。 
第壹行是 2*N个非负整数 s1, s2, …, s2N,每四个数里面用三个空格隔开分离,个中s 表示编号为 i 的健儿的初步分数。 
其三行是 2*N个正整数 w1, w2, …, w2N,每两个数以内用二个空格隔断,个中 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 }

 

出口格式

出口唯有一行,包涵一个整数,即 Wrangler 轮竞赛截止后,排名第 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