瑞士轮 归并排序 洛谷P1309

此题如果每次比赛后都sort，会TLE，只能得60分

因为sort是针对无规律随机数，而此题每次比赛后都会隐性地出现两个有序数组（win[]和lose[]），故采用归并排序能够节省很大时间

800ms·AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
int n,r,q;
struct node{
    int p,s,n;
};
node *win;
node *lose;
node *a;
bool cmp(node a, node b)
{
    if(a.s==b.s)
        return a.n<b.n;
    return a.s>b.s;
}
void mergewl()
{
    int i=0,j=0,k=0;//i是win[]的下标，j是lose[]的下标，k是a[]的下标
    while(i<=n-1&&j<=n-1){
        if(cmp(win[i],lose[j]))
            a[k++]=win[i++];
        else
            a[k++]=lose[j++];
    }
    if(i==n)
        while(j<=n-1) a[k++]=lose[j++];
    else
        while(i<=n-1) a[k++]=win[i++];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>r>>q;
    a=new node [n*2];
    win=new node [n];
    lose=new node [n];
    for(int i=0;i<2*n;i++)
    {
        cin>>a[i].s;
        a[i].n=i+1;
    }
    for(int i=0;i<2*n;i++)  
        cin>>a[i].p;
    sort(a,a+n*2,cmp);
    for(int j=0;j<r;j++)
    {
        for(int i=0;i<2*n;i+=2)
            if(a[i].p>a[i+1].p)
            {
                a[i].s++;
                win[i/2]=a[i];
                lose[i/2]=a[i+1];
            }
            else{
                a[i+1].s++;
                lose[i/2]=a[i];
                win[i/2]=a[i+1];
            }
        mergewl();//归并排序
    }
    cout<<a[q-1].n;
    delete [] a,win,lose;//new之后delete，防止内存泄露
    return 0;
}