merge sort(自用）

首先来看一下这道题目# P1309 [NOIP 2011 普及组] 瑞士轮## 题目背景在双人对决的竞技性比赛如乒乓球、羽毛球、国际象棋中最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少每场都紧张刺激但偶然性较高。后者的特点是较为公平偶然性较低但比赛过程往往十分冗长。本题中介绍的瑞士轮赛制因最早使用于 1895 年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中既保证了比赛的稳定性又能使赛程不至于过长。## 题目描述$2 \times N$ 名编号为 $1\sim 2\times N$ 的选手共进行 $R$ 轮比赛。每轮比赛开始前以及所有比赛结束后都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前的排名有关第 $1$ 名和第 $2$ 名、第 $3$ 名和第 $4$ 名、……、第 $2\times K - 1 $ 名和第 $2\times K$ 名、…… 、第 $2\times N - 1$ 名和第 $2\times N$ 名各进行一场比赛。每场比赛胜者得 $1$ 分负者得 $0$ 分。也就是说除了首轮以外其它轮比赛的安排均不能事先确定而是要取决于选手在之前比赛中的表现。现给定每个选手的初始分数及其实力值试计算在 $R$ 轮比赛过后排名第 $Q$ 的选手编号是多少。我们假设选手的实力值两两不同且每场比赛中实力值较高的总能获胜。## 输入格式第一行是三个正整数 $N,R,Q$每两个数之间用一个空格隔开表示有 $2\times N $ 名选手、$R$ 轮比赛以及我们关心的名次 $Q$。第二行是 $2\times N$ 个非负整数 $s_1, s_2,\dots, s_{2\times N}$每两个数之间用一个空格隔开其中 $s_i $ 表示编号为 $i$ 的选手的初始分数。第三行是 $2\times N$ 个正整数 $w_1,w_2,\dots,w_{2\times N}$每两个数之间用一个空格隔开其中 $w_i$ 表示编号为 $i$ 的选手的实力值。## 输出格式一个整数即 $R$ 轮比赛结束后排名第 $Q$ 的选手的编号。## 输入输出样例 #1### 输入 #12 4 27 6 6 710 5 20 15### 输出 #11## 说明/提示【样例解释】【数据范围】对于 $30\%$ 的数据$1\le N\le 100$对于 $50\%$ 的数据$1\le N\le 10000$对于 $100\%$ 的数据$1\le N\le 10^5,1\le R\le 50,1\le Q\le 2\times N,0\le s_1, s_2,\dots,s_{2\times N}\le 10^8,1\le w_1, w_2 , \dots, w_{2\times N}\le 10^8$。noip2011 普及组第 3 题。#include iostream #include algorithm #include cmath using namespace std; struct player{ int id; int score; int power; }p[200005]; bool cmp(player a,player b){ if(a.scoreb.score)return a.idb.id; return a.scoreb.score; } int main(){ int n,r,q; cinnrq; for(int i1;i2*n;i)cinp[i].score; for(int i1;i2*n;i){ p[i].idi; cinp[i].power; } for(int i1;ir;i){ sort(p1,p2*n1,cmp); for(int j1;j2*n-1;j2){ if(p[j].powerp[j1].power)p[j].score; else p[j1].score; } } sort(p1,p2*n1,cmp); coutp[q].id; getchar(); getchar(); return 0; }对于小数量的数据这样做确实可以但随着数据量扩大例如n或r较大时会严重超时。注意到每轮的获胜组与败者组的相对顺序并没有改变故可简单引入归并排序解决。#include iostream #include algorithm #include cmath using namespace std; struct player{ int id; int score; int power; }p[200005],winner[100005],loser[100005]; bool cmp(player a,player b){ if(a.scoreb.score)return a.idb.id; return a.scoreb.score; } int main(){ int n,r,q; cinnrq; for(int i1;i2*n;i)cinp[i].score; for(int i1;i2*n;i){ p[i].idi; cinp[i].power; } sort(p1,p2*n1,cmp); while(r--){ int w1,l1; for(int i1;i2*n;i2){//每轮比赛开始后将胜者存进winner数组败者存进loser if(p[i].powerp[i1].power){ p[i].score;//别忘了胜者分数1 winner[w]p[i]; loser[l]p[i1]; } else{ p[i1].score; winner[w]p[i1]; loser[l]p[i]; } } int i1,j1,k1; while(iwjl){//开始归并排序从高到低将winner和loser合并进p if(cmp(winner[i],loser[j]))p[k]winner[i]; else p[k]loser[j]; } while(iw)p[k]winner[i];//处理最后一位数 while(jl)p[k]loser[j]; } coutp[q].id; return 0; }