0025：2011年NOIp普及组真题——瑞士轮题解

题目链接：https://www.luogu.com.cn/problem/P1309

如果是新手可能马上会想到sort排序，每比一次就排一次，但是这样的时间复杂度有点高，只有60分；

这是因为每次比完赛会产生两个有序数列（输/赢），只需要把这两个有序数列合并成一个有序数列，而sort则是排了所有的数，显然浪费了时间

一提到有序数列，会想到归并排序——由于两个有序数列是现成的，所以只要并就行了，省了不少时间，可以AC

上代码：

#include<bits/stdc++.h>   
using namespace std;  
int n,r,q;  
int a[200100],s[200100],w[200100],win[200100],lose[200100];//a——序号，s——分数，w——战力  
bool cmp(int a,int b){//排序的时候判断大小（用标号）
     if(s[a]==s[b]){
         return a<b;
    }
      return s[a]>s[b];
}  
void Q(){//归并排序——并
    int i,j;  
    i=j=1,a[0]=0;  
    while(i<=win[0]&&j<=lose[0]){//输赢两个有序序列，所以直接并
        if(cmp(win[i],lose[j]))
            a[++a[0]]=win[i++];//回到a（序号）数组  
        else   
            a[++a[0]]=lose[j++];
    }    
    while(i<=win[0])a[++a[0]]=win[i++];  
    while(j<=lose[0])a[++a[0]]=lose[j++];//处理掉剩余的数       
}  
int main(){  
    cin>>n>>r>>q;
    n*=2;  
    for(int i=1;i<=n;i++){
        cin>>s[i];  
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
        a[i]=i;
    }  
    sort(a+1,a+n+1,cmp);//先快排一次 
    for(int i=1;i<=r;i++){
        win[0]=lose[0]=0;//0的正好没用，用来计数 
        for(int j=1;j<=n;j+=2){
            if(w[a[j]]>w[a[j+1]]){//判断哪方胜利
                s[a[j]]++;
                win[++win[0]]=a[j];
                lose[++lose[0]]=a[j+1];//加入
            }  
            else{
                s[a[j+1]]++; 
                win[++win[0]]=a[j+1];  
                lose[++lose[0]]=a[j];  
            }
        }    
        Q();          
    }
    cout<<a[q];//结束
    return 0;  
}