题目描述

在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制，因最早使用于 1895 年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长

输入描述:

第一行是三个正整数 N,R ,Q ,每两个数之间用一个空格隔开，表示有 2 x N 名选手、 R 轮比赛，以及我们关心的名次 Q 。
第二行是 2 x N 个非负整数 ，每两个数之间用一个空格隔开，其中 表示编号为 i 的选手的初始分数。 
第三行是 2 x N 个正整数 ，每两个数之间用一个空格隔开，其中 表示编号为 i 的选手的实力值。

输出描述:

一个整数，即 R 轮比赛结束后，排名第 Q 的选手的编号。

示例1

输入
2 4 2 
7 6 6 7 
10 5 20 15
输出
1
说明

备注:

对于 30% 的数据， ；
对于 50% 的数据， ；
对于 100% 的数据， 。

解答

看了一眼数据大小，我们可以知道用快排肯定会TLE，自己手写模拟试了试，果真只得了60分，因此我们需要改进排序算法。

这里我们可以用归并排序（时间复杂度），归并排序的思想就是对两个有序的数组进行操作，然后开另一个数组为两个数组大小之和。设两个指针p1,p2，开始初始化为1。当两个指针中的任何一个没有到最后时，就比较指针所指的数，将更大的数进入第三个数组，然后把该数所在的原数组的指针后移，反复进行上述操作。这可以节省快排的时间，但注意需要清零。在这道题里，对于这两个数组，我们把赢的放一起、输的放一起（都用结构体），由于在在过程中我们合并的数组排列是有序的，所以将两个人进行比较后，胜者放在胜者组，将胜者放一起也肯定是有序的（可以自己想想）。如果指针到头了，那我们就把没到头的那一个数组的后面的所有数都搬到合并数组的空位，然后就得到有序的合并数组了。注意对指针进行清零操作。

代码： 
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=200010;
int n,r,q;
struct player
{
	int s; //score
	int p; //power
	int num; //number
}a[maxn],win[maxn],lose[maxn],c[maxn];
bool cmp(const player &a,const player &b)
{
	if(a.s!=b.s) return a.s>b.s;
	else return a.num<b.num;
}
int p1,p2;
int main()
{
	scanf("%d%d%d",&n,&r,&q);
	for(int i=1;i<=2*n;i++)
	{
		scanf("%d",&a[i].s);
		a[i].num=i;
	}
	for(int i=1;i<=2*n;i++)
	{
		scanf("%d",&a[i].p);
	}
	sort(a+1,a+2*n+1,cmp);
	for(int i=1;i<=2*n;i++)
	{
		c[i]=a[i];
	}
	while(r--)
	{
		int t1=0,t2=0;
		for(int i=1;i<=2*n;i+=2)
		{
			if(c[i].p>c[i+1].p)	
			{
				c[i].s++;
				win[++t1]=c[i];
				lose[++t2]=c[i+1];
			}
			else 
			{
				c[i+1].s++;
				win[++t1]=c[i+1];
				lose[++t2]=c[i];
			}
		}	
//		for(int i=1;i<=2*n;i++)
//		{
//			cout<<c[i].num<<' '<<c[i].s<<endl;
//		}
//		cout<<win[1].num<<win[2].num<<lose[1].num<<lose[2].num;
		p1=1,p2=1;
		int t=0;
		while(p1<=n&&p2<=n)
		{
			if(win[p1].s!=lose[p2].s)
			{
				if(win[p1].s>lose[p2].s)
				{
					c[++t]=win[p1];
					p1++;
				}
				else
				{
					c[++t]=lose[p2];
					p2++;
				}
			}
			else
			{
				if(win[p1].num<lose[p2].num)
				{
					c[++t]=win[p1];
					p1++;
				}
				else
				{
					c[++t]=lose[p2];
					p2++;
				}	
			}
		}
		if(p1==n+1)
		{
			while(p2<=n)
			{
				c[++t]=lose[p2];
				p2++;
			}
		}
		if(p2==n+1)
		{
			while(p1<=n)
			{
				c[++t]=win[p1];
				p1++;
			}
		}
	} 
	printf("%d",c[q].num);
	
	return 0;
}


来源：Rem_Inory