P1309 瑞士轮 未完成 60

题目背景

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

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

题目描述

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

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

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

输入输出格式

输入格式:

输入文件名为swiss.in 。

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

第二行是2*N 个非负整数s1, s2, …, s2N,每两个数之间用一个空格隔开,其中 si 表示编号为i 的选手的初始分数。 第三行是2*N 个正整数w1 , w2 , …, w2N,每两个数之间用一个空格隔开,其中 wi 表示编号为i 的选手的实力值。

输出格式:

输出文件名为swiss.out。

输出只有一行,包含一个整数,即R 轮比赛结束后,排名第 Q 的选手的编号。

输入输出样例

输入样例#1:

2 4 2 
7 6 6 7 
10 5 20 15 

输出样例#1:

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。

noip2011普及组第3题。

 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

用Python分析苹果公司股价数据

❈ 作者:酱油哥,清华程序猿、IT非主流 专栏地址:https://zhuanlan.zhihu.com/c_147297848 ❈ 要点抢先看 1.csv数...

35560
来自专栏机器学习从入门到成神

一道面试题到卡特兰数及其应用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

12520
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

11430
来自专栏赵俊的Java专栏

用 Python 分析 YouTube 百万条数据

51320
来自专栏WOLFRAM

用 Wolfram 语言来做2017年高考数学试题之天津理科卷

18940
来自专栏ACM算法日常

当七夕遇上算法竞赛

  七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去T...

14920
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(下)

在上一篇里,我们学习了“自主角色”的一些基本行为:寻找(seek)、避开(flee)、到达(arrive)、追捕(pursue)、躲避(evade)、漫游(wa...

280100
来自专栏北京马哥教育

用Python分析苹果公司股价数据

专栏地址:https://zhuanlan.zhihu.com/c_147297848

48900
来自专栏数据结构与算法

BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

首先把给出的式子移项,我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

15920
来自专栏Python中文社区

用Python分析苹果公司股价数据

专栏地址:https://zhuanlan.zhihu.com/c_147297848

11120

扫码关注云+社区

领取腾讯云代金券