时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
一、题目内容
题目描述
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制，因最早使用于 1895 年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长
输入描述
第一行是三个正整数 N,R ,Q ,每两个数之间用一个空格隔开，表示有 2 x N 名选手、 R 轮比赛，以及我们关心的名次 Q 。
第二行是 2 x N 个非负整数 s1,s2,…,s2N ，每两个数之间用一个空格隔开，其中 si 表示编号为 i 的选手的初始分数。
第三行是 2 x N 个正整数 w1,w2,…,w2N，每两个数之间用一个空格隔开，其中 wi 表示编号为 i 的选手的实力值。
输出描述
一个整数，即 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。
二、解题思路
首先从备注中看，输入的样本数据量可能会很大，假如我们使用快排，时间复杂度必定不符合一般性要求，因此需要改进排序算法。
这道题中，每一轮比赛，会产生胜者和败者，我们可以将这两者分别放在胜者组和败者组（使用结构体，并且排序插入），然后再将胜者组和败者组合并到一个数组中（进行排序），可能大家都想到了，这就是归并排序(时间复杂度O(N))，这将节省快排的时间。
归并排序的思想就是将两个有序的数组进行操作，然后开另一个数组为两个数组大小之和。设两个指针p1，p2，开始初始化为1.当两个指针中的任何一个没有到达最后时，就比较指针所指的数，将更大的数进入第三个数组，然后把该数所在的原数组的指针后移，反复进行上述操作。
代码实操：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, k;
int s[N], w[N], q[N], q0[N], q1[N];
bool cmp(int a, int b)
{
if (s[a] != s[b]) return s[a] > s[b];
return a < b;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n * 2; i ++ ) scanf("%d", &s[i]);
for (int i = 0; i < n * 2; i ++ ) scanf("%d", &w[i]);
for (int i = 0; i < n * 2; i ++ ) q[i] = i;
//将所有同学编号按照分数、编号进行排序（规则：总分大者优先，编号小者优先）
sort(q, q + n * 2, cmp);
//进行每轮的比赛 每轮比赛会有n个同学分数+0（败者），另外n个同学分数+1（胜者），这两者内部都是有序的，这里使用二路归并算法。
//总的时间复杂度O(MlogN+NR)
while (m -- )
{
int t0 = 0, t1 = 0;
for (int i = 0; i < n * 2; i += 2)
{
int a = q[i], b = q[i + 1];
if (w[a] < w[b])
{
s[b] ++ ;
q0[t0 ++ ] = a;
q1[t1 ++ ] = b;
}
else
{
s[a] ++ ;
q0[t0 ++ ] = b;
q1[t1 ++ ] = a;
}
}
//每轮比赛后进行重排
int i = 0, j = 0, t = 0;
while (i < t0 && j < t1)
if (cmp(q0[i], q1[j]))
q[t ++ ] = q0[i ++ ];
else
q[t ++ ] = q1[j ++ ];
while (i < t0) q[t ++ ] = q0[i ++ ];
while (j < t1) q[t ++ ] = q1[j ++ ];
}
printf("%d\n", q[k - 1] + 1);
return 0;
}
