1309 瑞士轮
难度：普及/提高-
题目类型：分治
提交次数：2
涉及知识：归并、结构体
题目背景
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折衷，既保证了比赛的稳定性，又能使赛程不至于过长。
题目描述
2*N 名编号为 1~2N 的选手共进行R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。
每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1 名和第2 名、第 3 名和第 4名、……、第2K – 1 名和第 2K名、…… 、第2N – 1 名和第2N名，各进行一场比赛。每场比赛胜者得1 分，负者得 0 分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。
现给定每个选手的初始分数及其实力值，试计算在R 轮比赛过后，排名第 Q 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。
输入输出格式
输入格式：
输入文件名为swiss.in 。
输入的第一行是三个正整数N、R 、Q，每两个数之间用一个空格隔开，表示有 2*N 名选手、R 轮比赛，以及我们关心的名次 Q。
第二行是2*N 个非负整数s1, s2, …, s2N，每两个数之间用一个空格隔开，其中 si 表示编号为i 的选手的初始分数。 第三行是2*N 个正整数w1 , w2 , …, w2N，每两个数之间用一个空格隔开，其中 wi 表示编号为i 的选手的实力值。
输出格式：
输出文件名为swiss.out。
输出只有一行，包含一个整数，即R 轮比赛结束后，排名第 Q 的选手的编号。
输入输出样例
2 4 2 7 6 6 7 10 5 20 15
1
说明
【样例解释】
【数据范围】
对于30% 的数据，1 ≤ N ≤ 100；
对于50% 的数据，1 ≤ N ≤ 10,000 ；
对于100%的数据，1 ≤ N ≤ 100,000，1 ≤ R ≤ 50，1 ≤ Q ≤ 2N，0 ≤ s1, s2, …, s2N≤10^8，1 ≤w1, w2 , …, w2N≤ 10^8。
noip2011普及组第3题。
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 using namespace std; 5 int n, r, q; 6 struct player{ 7 int num; 8 int s; 9 int w; 10 player(int numm=0, int ss=0, int ww=0):num(numm), s(ss), w(ww){}; 11 bool operator<(const player&p1)const{ 12 if(s!=p1.s) 13 return s > p1.s; 14 else 15 return num < p1.num; 16 } 17 }; 18 vector<player>p; 19 int main(){ 20 int i; 21 int s[200010]; 22 int w[200010]; 23 cin>>n>>r>>q; 24 vector<player>win(n); 25 vector<player>lose(n); 26 for(i = 0; i < (n<<1); i++) 27 cin>>s[i]; 28 for(i = 0; i < (n<<1); i++) 29 cin>>w[i]; 30 for(i = 0; i < (n<<1); i++) 31 p.push_back(player(i+1, s[i], w[i])); 32 sort(p.begin(), p.end()); 33 while(r--){ 34 int m = 0; 35 for(i = 0; i < (n<<1); i=i+2){ 36 if(p[i].w>p[i+1].w){ 37 p[i].s++; 38 win[m] = p[i]; 39 lose[m] = p[i+1]; 40 } 41 else { 42 p[i+1].s++; 43 win[m] = p[i+1]; 44 lose[m] = p[i]; 45 } 46 m++; 47 } 48 /*for(i = 0; i < n; i++){ 49 cout<<"win:"<<endl<<win[i].num<<" "<<win[i].s<<" "<<win[i].w<<endl; 50 } 51 cout<<endl; 52 for(i = 0; i < n; i++){ 53 cout<<"lose:"<<endl<<lose[i].num<<" "<<lose[i].s<<" "<<lose[i].w<<endl; 54 } 55 cout<<endl;*/ 56 int j = 0, k = 0, l = 0; 57 while(j<n&&k<n){//merge少了一部分！！ 58 if(win[j].s<lose[k].s) 59 p[l++] = lose[k++]; 60 else if(win[j].s==lose[k].s){ 61 if(win[j].num<lose[k].num) 62 p[l++] = win[j++]; 63 else p[l++] = lose[k++]; 64 } 65 else p[l++] = win[j++]; 66 } 67 while(j<n) p[l++] = win[j++]; 68 while(k<n) p[l++] = lose[k++]; 69 /*for(i = 0; i < (n<<1); i++){ 70 cout<<p[i].num<<" "<<p[i].s<<" "<<p[i].w<<endl; 71 } 72 cout<<endl;*/ 73 } 74 cout<<p[q-1].num; 75 return 0; 76 }
备注：
思路老师讲过了，每场比赛后，将胜利者与失败者分成两个有序数组，并合并为一个有序数组，因为所有胜利者和所有失败者内部排名是不会变的，所以就是一个merge的过程。
累死宝宝了。犯了N多个错误，一次一次一个一个排查。对操作符重载理解的不够深刻，还以为重载之后vector就自动变成优先队列了，还发愁了半天怎么处理这个问题……这也太蠢了。重载是为了sort。。另外构造函数忘了初始化，导致win和lose两个vector一直定义不了；最开始没设m，直接用的i，于是各种溢出，检查了半天，加了m之后，什么时候清零，什么时候加一又出问题。最坑爹的错误就是居然把merge写丢了两行；还有由于初始和实力值是分别输入的，在输入那块略麻烦一点；最后，数组又开小了，没注意数据规模。