wikioi 1132 瑞士轮 (noip2011)

分析：

首先有一个不断快排的做法，好像会超时。

正解是归并。

先快排一次。

之后就是归并排序。

先将胜利的人加上1分，并放入一个win数组。

将失败的人放入一个lose数组里。

最后归并到原数组中。

这个题原本想到了正解，但是倒在了细节上。。

代码：

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
using namespace std;  
int n,r,q,i,j,ji;  
struct node  
{  
    int s,p,ii;  
}a[200010],w[100010],l[100010];  
  
bool cmp(node a,node b)  
{  
    if (a.s==b.s) return a.ii<b.ii;  
    return a.s>b.s;  
}  
int main()  
{    
    freopen("swiss.in","r",stdin);  
    freopen("swiss.out","w",stdout);  
    cin>>n>>r>>q; n*=2;  
    for ( i=1;i<=n;++i) scanf("%d",&a[i].s),a[i].ii=i;  
    for ( j=1;j<=n;++j) scanf("%d",&a[j].p);  
    sort(a+1,a+1+n,cmp);  
    for ( ji=1;ji<=r;ji++)  
     {    
        int wi=1,lo=1;  
        for ( i=1;i<=n;i+=2)  
        {  
            if (a[i].p<a[i+1].p) w[wi++]=a[i+1],l[lo++]=a[i];   
            else if (a[i].p>a[i+1].p)l[lo++]=a[i+1],w[wi++]=a[i];  
        }  
        wi--;lo--;  
        for ( i=1;i<=n/2;i++) w[i].s++;  
        int x=1,y=1;  
        i=0;  
        while( x<=n/2 && y<=n/2)  
        {  
            if (w[x].s>l[y].s) a[++i]=w[x++];  
            if (w[x].s<l[y].s) a[++i]=l[y++];  
            if (w[x].s==l[y].s&&w[x].ii>l[y].ii) a[++i]=l[y++];  
            if (w[x].s==l[y].s&&w[x].ii<l[y].ii) a[++i]=w[x++];  
         }  
         if (x>n/2)   
        while (y<=n/2) a[++i]=l[y++];        
        else while (x<=n/2) a[++i]=w[x++];  
     }  
     printf("%d",a[q].ii);  
}

补充：软件开发 , C++ ,