时间限制：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;
}