時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 131072K，其他語言262144K

一、題目內容

題目描述

在雙人對決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環(huán)賽。前者的特點是比賽場數(shù)少，每場都緊張刺激，但偶然性較高。后者的特點是較為公平，偶然性較低，但比賽過程往往十分冗長。
本題中介紹的瑞士輪賽制，因最早使用于 1895 年在瑞士舉辦的國際象棋比賽而得名。它可以看作是淘汰賽與循環(huán)賽的折中，既保證了比賽的穩(wěn)定性，又能使賽程不至于過長

輸入描述

第一行是三個正整數(shù) N,R ,Q ,每兩個數(shù)之間用一個空格隔開，表示有 2 x N 名選手、 R 輪比賽，以及我們關心的名次 Q 。
第二行是 2 x N 個非負整數(shù) s1,s2,…,s2N? ，每兩個數(shù)之間用一個空格隔開，其中 si? 表示編號為 i 的選手的初始分數(shù)。
第三行是 2 x N 個正整數(shù) w1,w2,…,w2N，每兩個數(shù)之間用一個空格隔開，其中 wi? 表示編號為 i 的選手的實力值。

輸出描述

一個整數(shù)，即 R 輪比賽結束后，排名第 Q 的選手的編號。

示例1

輸入

2 4 2
7 6 6 7
10 5 20 15

輸出

1

說明

圖1

備注

對于 30% 的數(shù)據(jù)， 1≤N≤100；
對于 50% 的數(shù)據(jù)， 1≤N≤10,000；
對于 100% 的數(shù)據(jù)， 1≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤s1,s2,…,s2N≤10^8, 1≤w1,w2,…,w2N≤10^8。

二、解題思路

首先從備注中看，輸入的樣本數(shù)據(jù)量可能會很大，假如我們使用快排，時間復雜度必定不符合一般性要求，因此需要改進排序算法。

這道題中，每一輪比賽，會產(chǎn)生勝者和敗者，我們可以將這兩者分別放在勝者組和敗者組（使用結構體，并且排序插入），然后再將勝者組和敗者組合并到一個數(shù)組中（進行排序），可能大家都想到了，這就是歸并排序(時間復雜度O(N))，這將節(jié)省快排的時間。

歸并排序的思想就是將兩個有序的數(shù)組進行操作，然后開另一個數(shù)組為兩個數(shù)組大小之和。設兩個指針p1，p2，開始初始化為1.當兩個指針中的任何一個沒有到達最后時，就比較指針所指的數(shù)，將更大的數(shù)進入第三個數(shù)組，然后把該數(shù)所在的原數(shù)組的指針后移，反復進行上述操作。

代碼實操：

#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;
    //將所有同學編號按照分數(shù)、編號進行排序（規(guī)則：總分大者優(yōu)先，編號小者優(yōu)先）
    sort(q, q + n * 2, cmp);
    //進行每輪的比賽 每輪比賽會有n個同學分數(shù)+0（敗者），另外n個同學分數(shù)+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;
}