洛谷P1309 瑞士轮(归并排序)
题目背景
在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公平,偶然性较低,但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制,因最早使用于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 的选手的编号。
输入输出样例
2 4 2
7 6 6 7
10 5 20 15
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题。
思路:
排序,不过快排也会超时,需要用归并排序,因为每次竞赛后,胜利者和失败者依然是按照得分从大到小的顺序产生的。
代码:
归并排序:
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn=;
int n,r,q,size;
struct competitor
{
int num,score,force;
}comp[maxn*],winner[maxn],loser[maxn]; void read(int &now)
{
now=;
char word=getchar();
while(word<'' || word>'')
word=getchar();
while(word>='' && word<='')
now=now*+word-'',word=getchar();
}
void output(int now)
{
int num=;
char c[];
while(now) c[++num]=(now%)+'',now/=;
while(num) putchar(c[num--]);
putchar('\n');
} bool cmpSC(competitor x,competitor y)
{
if(x.score == y.score)
return x.num < y.num;
return x.score > y.score;
}
void mergesort()
{
int nowl=,nowr=,nowc=;
while(nowl<=size && nowr<=size)
{
if(winner[nowl].score < loser[nowr].score)
comp[++nowc]=loser[nowr++];
else if(winner[nowl].score > loser[nowr].score)
comp[++nowc]=winner[nowl++];
else if(winner[nowl].num < loser[nowr].num)
comp[++nowc]=winner[nowl++];
else
comp[++nowc]=loser[nowr++];
}
while(nowl<=size)
comp[++nowc]=winner[nowl++];
while(nowr<=size)
comp[++nowc]=loser[nowr++]; /*while(nowc<n)
{
if(nowl>size)
{
while(nowr<=size)
comp[++nowc]=loser[nowr++];
break;
}
if(nowr>size)
{
while(nowl<=size)
comp[++nowc]=winner[nowl++];
break;
}
if(winner[nowl].score<loser[nowr].score||(winner[nowl].score==loser[nowr].score && winner[nowl].num>loser[nowr].num))
comp[++nowc]=loser[nowr++];
else
comp[++nowc]=winner[nowl++];
}*/
}
void march()
{
int now=;
//sort(comp+1,comp+1+n*2,cmpSC);
size=;
while(now<=n)
{
if(comp[now].force > comp[now+].force)
++comp[now].score,winner[++size]=comp[now],loser[size]=comp[now+];
else
++comp[now+].score,winner[++size]=comp[now+],loser[size]=comp[now];
now+=;
}
mergesort();
} int main()
{
read(n);read(r);read(q);
n<<=;
for(int i=;i<=n;i++)
{
read(comp[i].score);
comp[i].num=i;
}
for(int i=;i<=n;i++)
read(comp[i].force);
sort(comp+,comp++n,cmpSC);
while(r--)
march();
output(comp[q].num);
/*for(int i=1;i<=n*2;i++)
printf("%d %d\n",comp[i].num,comp[i].score);*/
return ;
}
AC
快排(60分 TLE四个点):
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn=;
int n,r,q;
struct competitor
{
int num,score,force;
}comp[maxn*]; void read(int &now)
{
now=;
char word=getchar();
while(word<'' || word>'')
word=getchar();
while(word>='' && word<='')
now=now*+word-'',word=getchar();
}
void output(int now)
{
int num=;
char c[];
while(now) c[++num]=(now%)+'',now/=;
while(num) putchar(c[num--]);
putchar('\n');
} bool cmpSC(competitor x,competitor y)
{
if(x.score == y.score)
return x.num > y.num;
return x.score < y.score;
}
void march()
{
int now=n*;
sort(comp+,comp++n*,cmpSC);
while(now)
{
if(comp[now].force > comp[now-].force)
++comp[now].score;
else
++comp[now-].score;
now-=;
}
} int main()
{
read(n);read(r);read(q);
for(int i=;i<=*n;i++)
{
read(comp[i].score);
comp[i].num=i;
}
for(int i=;i<=*n;i++)
read(comp[i].force);
int now=r;
while(now--)
march();
sort(comp+,comp++n*,cmpSC);
output(comp[n*-q+].num);
/*for(int i=1;i<=n*2;i++)
printf("%d %d\n",comp[i].num,comp[i].score);*/
return ;
}
TLE
最新文章
- Spark standlone安装与配置
- 从API请求数据的方法(主要适用于tp5)
- POJ 2838 单调队列
- android 事件监听
- M6: 使用摄像头(CameraCaptureUI)
- Python Backup Files
- Tomcat SSL 设置
- POJ 3126 Prime Path BFS搜索
- JSF session的用法
- C 语言函数指针
- php数组操作函数
- js 计算两个日期之间的周数
- 如何改变word修订模型下的视图
- DOM元素对象的属性和方法(1)
- GitHub For Beginners: Commit, Push And Go
- LayUI之table数据表格获取行、行高亮等相关操作
- asp.net core上使用Redis探索(2)
- c/c++ 网络编程 UDP 发送端 bind 作用
- Oracle查询语句导致CPU使用率过高问题处理
- [Pipy]利用pip2pi搭建本地pypi源
热门文章
- Nginx详解十:Nginx场景实践篇之Nginx静态资源场景配置
- selenium+python-文件下载(SendKeys)
- linux:安装Memcache并使用
- 繁简字转换(C#)
- Html 文字排版
- |ERROR|ERROR: missing data for column ";createtime"; (seg3 slice1 192.168.66.23:40001 pid=33370)之mysql换行符或者空格引起的问题
- Zabbix 3.2.6通过SNMP和iDRAC监控DELL服务器
- Select2 多层次赋值时异步赋值的问题
- 【Android】Bitmap加载图片错误 java.lang.OutOfMemoryError: bitmap size exceeds VM budget
- playbook role应用