解题思路

首先从备注中看，输入的样本数据量可能会很大，假如我们使用快排，时间复杂度必定不符合一般性要求，因此需要改进排序算法。

这道题中，每一轮比赛，会产生胜者和败者，我们可以将这两者分别放在胜者组和败者组（使用结构体，并且排序插入），然后再将胜者组和败者组合并到一个数组中（进行排序），可能大家都想到了，这就是归并排序(时间复杂度 O(N)) ，这将节省快排的时间。

归并排序的思想就是将两个有序的数组进行操作，然后开另一个数组为两个数组大小之和。设两个指针p1，p2，开始初始化为1.当两个指针中的任何一个没有到达最后时，就比较指针所指的数，将更大的数进入第三个数组，然后把该数所在的原数组的指针后移，反复进行上述操作。

AC代码

#include <bits/stdc++.h>
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()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n * 2; i++)
        cin >> s[i];
    for (int i = 0; i < n * 2; i++)
        cin >> 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++];
    }
	cout << q[k - 1] + 1;
    return 0;
}

题解

题面应该不难理解，就是每次相邻分数的两个人根据实力值进行比较，然后输赢加分，不断排序罢了。所以我们第一时间一定会想到 sort 来排序。可是 sort 排序是有巨大的时间浪费的。因为 sort 每次都要从头来一次排序，对于我们这种一部分数据变化（一半人加 $1$ 分）的情况下确有浪费。

这里我们观察特点，发现只有胜利者加 $1$ 分，其他的人不变。所以每轮比赛结束后，胜者和负者两个部分的内部顺序是不会被打乱的。所以快排就没有了随机数组中的优势。

很明显，由于两个部分都是有序的，合并两个部分使我们想到了一个东西————归并排序里的 $merge$ 函数。

如果你没有学过归并排序，我只能简单的描述一下：利用分治法将原数组/区间分为两个区间，对单独的区间进行归并排序，最后合并两个有序区间进到整个数组/区间里。其中合并有序区间的函数称之为 $merge$。

我们可以胜者进入队列 $A$，负者入队 $B$。这样A、B自身仍是有序的，直接 $merge$ 两个队列。

归并的方法是把两个队列的最大比较一下，把更大的先入队，最后把一个剩下的队列里的东西全加进去。

然后都是实现层面的问题了，我们结合代码分析一下：

#include <bits/stdc++.h>
using namespace std;
struct player // 我们可以用结构体储存选手信息
{
    int score, rank; // score 表示选手得分，rank 表示排名
};
int n, r, q;
player a[200005];
player A[100005];
player B[100005];
int w[200005];
bool cmp(player a, player b)
{
    if (a.score == b.score)
        return a.rank < b.rank;
    return a.score > b.score;
}
void merge() // 把AB归并到a中
{
    int i = 1, j = 1, k = 1; // 分别用来在AB以及a中移动的指针
    while (i <= n && j <= n)
    {
        if (A[i].score > B[j].score || (A[i].score == B[j].score && A[i].rank < B[j].rank))
        {
            a[k].score = A[i].score;
            a[k++].rank = A[i++].rank;
        }
        else
        {
            a[k].score = B[j].score;
            a[k++].rank = B[j++].rank;
        }
    }
    while (i <= n)
    {
        a[k].score = A[i].score;
        a[k++].rank = A[i++].rank;
    }
    while (j <= n)
    {
         a[k].score = B[j].score;
        a[k++].rank = B[j++].rank;
    }
}
int main()
{
    scanf("%d%d%d", &n, &r, &q);
    for (int i = 1; i <= 2 * n; i++)
    {
        scanf("%d", &a[i].score);
        a[i].rank = i;
    }
    for (int i = 1; i <= 2 * n; i++)
        scanf("%d", &w[i]);
    sort(a + 1, a + 2 * n + 1, cmp);
    for (int k = 1; k <= r; k++)
    {
        int tt = 1;
        for (int i = 1; i < 2 * n; i += 2)
        {
            if (w[a[i].rank] > w[a[i + 1].rank])
            {
                A[tt].score = a[i].score+1;
                A[tt].rank = a[i].rank;
                B[tt].score  =  a[i+1].score;
                B[tt].rank = a[i+1].rank;
                tt++;
            }
            else
            {
                A[tt].score = a[i+1].score+1;
                A[tt].rank = a[i+1].rank;
                B[tt].score  =  a[i].score;
                B[tt].rank = a[i].rank;
                tt++;
            }
        }
        merge(); // 归并一下，你就得到
    }
    printf("%d\n", a[q].rank);
    return 0;
}

$AC$ $Code$

#include <bits/stdc++.h>
using namespace std;
struct player
{
    int score, rank;
};
int n, r, q;
player a[200005];
player A[100005];
player B[100005];
int w[200005];
bool cmp(player a, player b)
{
    if (a.score == b.score)
        return a.rank < b.rank;
    return a.score > b.score;
}
void merge()
{
    int i = 1, j = 1, k = 1;
    while (i <= n && j <= n)
    {
        if (A[i].score > B[j].score || (A[i].score == B[j].score && A[i].rank < B[j].rank))
        {
            a[k].score = A[i].score;
            a[k++].rank = A[i++].rank;
        }
        else
        {
            a[k].score = B[j].score;
            a[k++].rank = B[j++].rank;
        }
    }
    while (i <= n)
    {
        a[k].score = A[i].score;
        a[k++].rank = A[i++].rank;
    }
    while (j <= n)
    {
         a[k].score = B[j].score;
        a[k++].rank = B[j++].rank;
    }
}
int main()
{
    scanf("%d%d%d", &n, &r, &q);
    for (int i = 1; i <= 2 * n; i++)
    {
        scanf("%d", &a[i].score);
        a[i].rank = i;
    }
    for (int i = 1; i <= 2 * n; i++)
        scanf("%d", &w[i]);
    sort(a + 1, a + 2 * n + 1, cmp);
    for (int k = 1; k <= r; k++)
    {
        int tt = 1;
        for (int i = 1; i < 2 * n; i += 2)
        {
            if (w[a[i].rank] > w[a[i + 1].rank])
            {
                A[tt].score = a[i].score+1;
                A[tt].rank = a[i].rank;
                B[tt].score  =  a[i+1].score;
                B[tt].rank = a[i+1].rank;
                tt++;
            }
            else
            {
                A[tt].score = a[i+1].score+1;
                A[tt].rank = a[i+1].rank;
                B[tt].score  =  a[i].score;
                B[tt].rank = a[i].rank;
                tt++;
            }
        }
        merge();
    }
    printf("%d\n", a[q].rank);
    return 0;
}

课里归并排序那一节课的题目就是引用这个