洛谷题解 P1309 【瑞士轮】

题目链接

这道题题意不难理解,开二倍N的空间,然后模拟即可。

如果我们每次更新分数后使用sort来排序将耗费大量的时间,因为sort的优越性在于随机数列,可以达到 $\Theta (N\log_2N)$的时间复杂度,但对于本题的有序数列(即每次处理后,胜者的队列与负者的队列仍然为降序)来说是一种浪费,所以会导致TLE,根据本题的特性,不难想到归并排序的思想来操作。

代码如下

#include<cstdio>
#include<algorithm>
int n,r,q;
struct person{
    int id;
    int s;
    int w;
}a[200005],win[100005],lose[100005],em;
int wn,ln;
inline bool cmp(person x,person y){
    return (x.s==y.s)?(x.id<y.id):(x.s>y.s);
}
void merge(){
    int w=1,l=1,i=1;
    while(w<=wn&&l<=ln){
        if(cmp(win[w],lose[l]))	
            a[i++]=win[w++];
        else
            a[i++]=lose[l++];
    }
    while(w<=wn)
        a[i++]=win[w++];
    while(l<=ln)
        a[i++]=lose[l++];
}	
int main(){
    scanf("%d %d %d",&n,&r,&q);
    n*=2;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].s);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].w);
    for(int i=1;i<=n;i++)
        a[i].id=i;
    std::sort(a+1,a+n+1,cmp);
    while(r--){
        wn=ln=0;
        for(int i=1;i<=n-1;i+=2){
            if(a[i].w>a[i+1].w){
                a[i].s++;
                win[++wn]=a[i];
                lose[++ln]=a[i+1];
            }
            else{
                a[i+1].s++;
                win[++wn]=a[i+1];
                lose[++ln]=a[i];
            }
        }
        merge();
    }
    printf("%d\n",a[q].id);
    return 0;
}

美化版本

#include <algorithm>
#include <cstdio>
int n, r, q;
struct person
{
    int id;
    int s;
    int w;
} a[200005], win[100005], lose[100005], em;
int wn, ln;
inline bool cmp(person x, person y)
{
    return (x.s == y.s) ? (x.id < y.id) : (x.s > y.s);
}
void merge()
{
    int w = 1, l = 1, i = 1;
    while (w <= wn && l <= ln)
    {
        if (cmp(win[w], lose[l]))
            a[i++] = win[w++];
        else
            a[i++] = lose[l++];
    }
    while (w <= wn)
        a[i++] = win[w++];
    while (l <= ln)
        a[i++] = lose[l++];
}
int main()
{
    scanf("%d %d %d", &n, &r, &q);
    n *= 2;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i].s);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i].w);
    for (int i = 1; i <= n; i++)
        a[i].id = i;
    std::sort(a + 1, a + n + 1, cmp);
    while (r--)
    {
        wn = ln = 0;
        for (int i = 1; i <= n - 1; i += 2)
        {
            if (a[i].w > a[i + 1].w)
            {
                a[i].s++;
                win[++wn] = a[i];
                lose[++ln] = a[i + 1];
            }
            else
            {
                a[i + 1].s++;
                win[++wn] = a[i + 1];
                lose[++ln] = a[i];
            }
        }
        merge();
    }
    printf("%d\n", a[q].id);
    return 0;
}