本文主要是介绍瑞士轮 （优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem F: 瑞士轮
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 60 Solved: 19
[Submit][Status][Web Board]
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，每两个数之间用一个空格隔开，其中 s 表示编号为 i 的选手的初始分数。
第三行是 2*N个正整数 w1, w2, …, w2N，每两个数之间用一个空格隔开，其中 w 表示编号为 i 的选手的实力值。
Output
输出只有一行，包含一个整数，即 R 轮比赛结束后，排名第 Q 的选手的编号。
Sample Input
2 4 2 7 6 6 7 10 5 20 15
Sample Output
1
HINT
输入输出样例说明：
| 本轮对阵 | 本轮结束后的得分 | ||||
| 选手编号 | / | ① | ② | ③ | ④ |
| 初始 | / | 7 | 6 | 6 | 7 |
| 第1轮 | ①—④ ②—③ | 7 | 6 | 7 | 8 |
| 第2轮 | ④—① ③—② | 7 | 6 | 8 | 9 |
| 第3轮 | ④—③ ①—② | 8 | 6 | 9 | 9 |
| 第4轮 | ③—④ ①—② | 9 | 6 | 10 | 9 |
数据范围：
对于 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。
NOIP2011 普及组 swiss
题目意思很简单，经过r次比赛后输出排名第k位的编号。
裸sort去暴力超时，想到一点：
赢的人，每人加一分后，在赢的组里面依旧是处于降序（有序）
输的人，在输的组里面依旧是处于降序（有序）
赢的人加输的人就等于总人数啦，也就是，
把两个有序的数组合并成一个有序的数组，时间复杂度O（N） 比sort 少了log（N）,AC:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<ctime>
#include<cctype>
#include<stack>
using namespace std;
#define mod 19999997
struct Node
{int sco;int power;int index;
} win[100005],lose[100005],a[200005];bool cmp(Node a,Node b)
{if(a.sco!=b.sco) return a.sco>b.sco;return a.index<b.index;
}
int n,r,q;
int merges()
{int w=0;int l=0;int i;for( i=1; w!=n&&l!=n; i++)if(win[w].sco>lose[l].sco)a[i]=win[w++];else if(win[w].sco==lose[l].sco){if(win[w].index<lose[l].index){a[i]=win[w++];}elsea[i]=lose[l++];}elsea[i]=lose[l++];if(l!=n) while(l<n) a[i++]=lose[l++];if(w!=n) while(w<n) a[i++]=win[w++];
}int main()
{scanf("%d%d%d",&n,&r,&q);for(int i=1; i<=2*n; i++){scanf("%d",&a[i].sco);a[i].index=i;}for(int i=1; i<=2*n; i++)scanf("%d",&a[i].power);sort(a+1,a+1+2*n,cmp);for(int i=0; i<r; i++){//for(int i=1;i<=2*n;i++)// cout<<a[i].sco<<" "<<a[i].power<<" "<<a[i].index<<endl;int x=0;int y=0;for(int j=1; j<2*n; j+=2)if(a[j].power>a[j+1].power)win[x]=a[j],lose[y++]=a[j+1],win[x++].sco++;elsewin[x]=a[j+1],lose[y++]=a[j],win[x++].sco++;merges();}cout<<a[q].index;return 0;
}
这篇关于瑞士轮 （优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
