Description

在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制，因最早使用于 1895 年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折衷，既保证了比赛的稳定性，又能使赛程不至于过长。

2*N 名编号为1~2N 的选手共进行R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前的排名有关：第 1 名和第2 名、第3 名和第4名、……、第2K – 1 名和第2K 名、…… 、第 2N – 1 名和第2N 名，各进行一场比赛。每场比赛胜者得1 分，负者得0 分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。
现给定每个选手的初始分数及其实力值，试计算在 R 轮比赛过后，排名第Q 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

Input

输入的第一行是三个正整数 N、R、Q，每两个数之间用一个空格隔开，表示有2*N 名选手、R 轮比赛，以及我们关心的名次Q。
第二行是 2*N 个非负整数s1, s2, …, s2N，每两个数之间用一个空格隔开，其中si 表示编号为i 的选手的初始分数。
第三行是 2*N 个正整数w1, w2, …, w2N，每两个数之间用一个空格隔开，其中wi 表示编号为i 的选手的实力值。

Output

输出只有一行，包含一个整数，即 R 轮比赛结束后，排名第Q 的选手的编号。

Sample Input

2 4 2
7 6 6 7
10 5 20 15

Sample Output

1

HINT

对于 30%的数据，1 ≤ N≤ 100；
对于 50%的数据，1 ≤ N≤ 10,000；
对于 100%的数据，1 ≤ N≤ 100,000，1 ≤ R≤ 50，1 ≤ Q≤ 2N，0 ≤ s1, s2, …, s2N ≤ 108，1 ≤ w1,w2, …, w2N ≤ 108。

题解

先一次快排预处理，然后归并。

因为对于赢的一组和输的一组，他们的相对位置是不会改变的。

这题调了一个半小时。。。因为一开始循环写了两个语句，用逗号隔开了，然后又加了一句，加了个分号，没加括号。。。然后最后发现有三处这样的错误。。。

不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号不要忘了加括号

我知道写的很丑。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200010;
struct node{
    int s,w,num;
}a[N],lose[N],win[N];
int n,r,q,cnt1=0,cnt2=0;
bool cmp(const node &c,const node &d){
    if (c.s==d.s) return c.num<d.num;
    return c.s>d.s;
}
void go(){
    cnt1=0,cnt2=0;
    for (int i=1;cnt2<n/2;i+=2){
        if (a[i].w>a[i+1].w){
            win[++cnt1].w=a[i].w; win[cnt1].s=a[i].s+1;win[cnt1].num=a[i].num;
            lose[++cnt2].w=a[i+1].w; lose[cnt2].s=a[i+1].s;lose[cnt2].num=a[i+1].num;
        }else{
            cnt1++;win[cnt1].w=a[i+1].w; win[cnt1].s=a[i+1].s+1;win[cnt1].num=a[i+1].num;
            lose[++cnt2].w=a[i].w; lose[cnt2].s=a[i].s;lose[cnt1].num=a[i].num;
        }
    }
        int i2=1,j2=1,cnt=0;
        for (;i2<=(n/2)&&j2<=(n/2);){
            if (win[i2].s>lose[j2].s){
                a[++cnt].s=win[i2].s;a[cnt].w=win[i2].w;a[cnt].num=win[i2].num;i2++;
            }else
            if (win[i2].s<lose[j2].s){
                a[++cnt].s=lose[j2].s;a[cnt].w=lose[j2].w;a[cnt].num=lose[j2].num;j2++;
            }else{
                if (win[i2].num<lose[j2].num){
                    a[++cnt].s=win[i2].s;a[cnt].w=win[i2].w;a[cnt].num=win[i2].num;i2++;
                }
                else{
                    a[++cnt].s=lose[j2].s;a[cnt].w=lose[j2].w;a[cnt].num=lose[j2].num;j2++;
                }
            }
        }
        for (;i2<=(n/2);i2++){
            a[++cnt].s=win[i2].s;a[cnt].w=win[i2].w;a[cnt].num=win[i2].num;
        }
        for (;j2<=(n/2);j2++){
            a[++cnt].s=lose[j2].s;a[cnt].w=lose[j2].w;a[cnt].num=lose[j2].num;
        }
}
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].num=i;
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=r;i++)    go();
    cout<<a[q].num;
}

 

版权声明：本文为liumengyue原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/liumengyue/p/5263400.html