瑞士轮_(归并，条件排序)

原题链接：P1309 [NOIP2011 普及组] 瑞士轮 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意

排序，2N名选手，按排名每每两人比赛，不重叠，胜者得一分，再排名比赛，重复R轮，要求输出查询选手编号的排名，同分按编号小的在前，有绝对实力条件，即给定选手实力，高的胜

思路

两个问题：

• 如何排序
• 如何做好映射

排序问题，两两之间比赛，赢的加一分，输的不加，这样来看，每笔一轮都有可能产生新的排名，但是局部来看，在赢的人里，原本排名高的依旧高，在输的人里，原本低的依旧低

也就是说每轮赢的数组和输的数组都是有序的，只要做一次归并就可以

映射问题，用索引表示排名，用数值表示编号，维护一个数组记录编号，这个数组是归并排序的结果数组，高分在前，但其本身没有排序信息，也就是利用其他条件进行排序，可以维护一个分数数组，用这个数组编写cmp函数进行大小比较

代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e6 + 10;
int n, r, q;
int a[N];
int s[N];
int w[N];
//输赢数组
int W[N], L[N];
 
bool cmp(int x, int y)
{
    if(s[x] == s[y]) return x < y;
    return s[x] > s[y];
}
 
 
void merge(int W[], int L[])
{
    int i = 1, j = 1, k = 1;
    while(i <= n / 2 && j <= n / 2)
    {
        if(cmp(W[i], L[j]))
        {
            a[k ++] = W[i ++];
        }
        else
        {
            a[k ++] = L[j ++];
        }
    }
 
    while(i <= n / 2)  a[k ++] = W[i ++];
    while(j <= n / 2)  a[k ++] = L[j ++];
}
 
 
 
int main()
{
    scanf("%d%d%d", &n, &r, &q);
 
    n *= 2;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &s[i]);
        a[i] = i;
    }
    
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &w[i]);
    }
 
    sort(a + 1, a + 1 + n, cmp);
 
    while(r --)
    {
        //输、赢单独来看结果依旧是顺序的，不需要重新排序，但是输赢两队需要归并排序
        for(int i = 1, j = 1; i <= n; i += 2, j ++)
        {
            if(w[a[i]] > w[a[i + 1]])
            {
                s[a[i]] ++;
                W[j] = a[i];
                L[j] = a[i + 1];
            }
            else
            {
                s[a[i + 1]] ++;
                W[j] = a[i + 1];
                L[j] = a[i];
            }
        }
        merge(W, L);
    }
 
    printf("%d\n", a[q]);
    return 0;
}