我们先来读题
题目背景
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长。
题目描述
名编号为 的选手共进行轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。
每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第 3名和第4名、……、第名和第K名、…… 、第名和第名，各进行一场比赛。每场比赛胜者得1分，负者得 0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。
现给定每个选手的初始分数及其实力值，试计算在轮比赛过后，排名第的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。
输入格式
第一行是三个正整数每两个数之间用一个空格隔开，表示有 名选手、轮比赛，以及我们关心的名次。
第二行是个非负整数，每两个数之间用一个空格隔开，其中表示编号为的选手的初始分数。 第三行是个正整数，每两个数之间用一个空格隔开，其中表示编号为的选手的实力值。
输出格式
一个整数，即轮比赛结束后，排名第的选手的编号。
输入输出样例
输入 #1
2 4 2
7 6 6 7
10 5 20 15
输出 #1
1
说明/提示
【样例解释】
【数据范围】
对于的数据，；
对于的数据，；
对于的数据，;
noip2011普及组第3题。
注意：是2N个队员！
具体实现
这一次还是要用到归并排序。归并排序代码：
void merge(int l,int mid,int r){
//l~mid
//mid+1 ~r
int i=l,j=mid+1,q=l;
while(i<=mid&&j<=r){
if(a[i]>a[j]){
t[q++]=a[j++];
}else{
t[q++]=a[i++];
}
}
while(i<=mid) t[q++]=a[i++];
while(j<=r) t[q++]=a[j++];
// t[l~r]
for(int x=l;x<=r;x++){
a[x]=t[x];
}
}
void mergeSort(int l,int r){
if(l>=r) return ;
int mid =(l+r)/2;
//1. 左右两边有序
mergeSort(l,mid);
mergeSort(mid+1,r);
//O（n） 合并
merge(l,mid,r);
}
我们来分析一下，题目中说是第几名，就和与它相邻的那一名比，也就是说按照排名比，此时比赛后，所有胜者的排名是不变的，因为大家都加一分，败者也是同理，所以他一定是会分成胜者和败者组，而他们都是有序的，所以函数是不需要的。
再来思考一个问题：一名队员有多个信息，例如编号，实力值，排名。该怎么办呢？分开写，这代码是不是太麻烦了，用二维数组，题目中那么多量，你确定方便？这时就由结构体来帮忙。代码:
typedef struct node{//队员信息结构体
int id;//编号
int cs;//分数
int w;//实力
}node;//名称：node
把它写在最外面，因为接下来要定义一些全局变量。
node xs[200010];//汇总
node win[100010];//赢
node lose[100010];//输
胜者组，败者组，看到了吧？
此时就改改函数吧，首先参数全部去掉，的值换掉，t的类型改变，循环终止条件换掉，判断的条件也要换一换，赋值时不用，改成，接下来的循环同理，最后赋值到。
疯狂修改时间……
先不要看下面的代码……
修改之后的代码：
//咳咳，我没骗你啊，代码其实在这
void merge(){//归并排序的应用
int i=1,j=1,q=1;//对应win,lose,t
node t[200010];//t
while(i<=n&&j<=n){//while 循环 不断将名次靠前的赋值到k
if(cmp(win[i],lose[j])){//如果win名次靠前
t[q++]=win[i++];
}else{//其他情况(相等或lose名次靠前)
t[q++]=lose[j++];
}
}
while(i<=n) t[q++]=win[i++];
while(j<=n) t[q++]=lose[j++];
for(int x=1;x<=2*n;x++){//将t中的值返还给a
xs[x]=t[x];
}
}
最后，再把主函数补充完整。
int main(int argc, char** argv) {//主函数
cin>>n>>r>>q;//输入 基本信息
for(int i=1;i<=2*n;i++){//输入基础分并添加编号
cin>>xs[i].cs;
xs[i].id=i;
}
for(int i=1;i<=2*n;i++){//输入实力值
cin>>xs[i].w;
}
sort(xs+1,xs+2*n+1,cmp);//一开始的混乱数据排序
for(int i=1;i<=r;i++){//经过每一轮比赛
k = 1;
for(int j=1;j<=2*n;j+=2){//每一位选手
if(xs[j].w > xs[j+1].w){//比较实力值
xs[j].cs++;
win[k]=xs[j];//j胜利
lose[k]=xs[j+1];//j+1输
k++;
}else{
xs[j+1].cs++;
win[k]=xs[j+1];//j+1赢
lose[k]=xs[j];//j失败
k++;
}
}
merge();//排序
}
cout<<xs[q].id;//输出第q名。
return 0;
}
最后，又到了完整代码
请勿抄袭！！！
#include<bits/stdc++.h>//万能头文件
using namespace std;
typedef struct node{//队员信息结构体
int id;//编号
int cs;//分数
int w;//实力
}node;//名称：node
node xs[200010];//汇总
node win[100010];//赢
node lose[100010];//输
//定义多个队员信息结构体
int n,r,q,k=1;
//对应题目中的人数，比赛场数，目标名次，对阵安排
bool cmp(node a,node b){//判断名次前后
if(a.cs > b.cs){//分数
return 1;//返回真值
}else if(a.cs == b.cs && a.id < b.id){//当分数一样且编号小时
return 1;//返回真值
}else{
return 0;//返回假值
}
}
void merge(){//归并排序的应用
int i=1,j=1,q=1;//对应win,lose,t
node t[200010];//t
while(i<=n&&j<=n){//while 循环 不断将名次靠前的赋值到k
if(cmp(win[i],lose[j])){//如果win名次靠前
t[q++]=win[i++];
}else{//其他情况(相等或lose名次靠前)
t[q++]=lose[j++];
}
}
while(i<=n) t[q++]=win[i++];
while(j<=n) t[q++]=lose[j++];
for(int x=1;x<=2*n;x++){//将t中的值返还给a
xs[x]=t[x];
}
}
int main(int argc, char** argv) {//主函数
cin>>n>>r>>q;//输入 基本信息
for(int i=1;i<=2*n;i++){//输入基础分并添加编号
cin>>xs[i].cs;
xs[i].id=i;
}
for(int i=1;i<=2*n;i++){//输入实力值
cin>>xs[i].w;
}
sort(xs+1,xs+2*n+1,cmp);//一开始的混乱数据排序
for(int i=1;i<=r;i++){//经过每一轮比赛
k = 1;
for(int j=1;j<=2*n;j+=2){//每一位选手
if(xs[j].w > xs[j+1].w){//比较实力值
xs[j].cs++;
win[k]=xs[j];//j胜利
lose[k]=xs[j+1];//j+1输
k++;
}else{
xs[j+1].cs++;
win[k]=xs[j+1];//j+1赢
lose[k]=xs[j];//j失败
k++;
}
}
merge();//排序
}
cout<<xs[q].id;//输出第q名。
return 0;
}