P1309 瑞士轮【洛谷算法习题】

P1309 瑞士轮网页链接P1309 瑞士轮题目背景在双人对决的竞技性比赛如乒乓球、羽毛球、国际象棋中最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少每场都紧张刺激但偶然性较高。后者的特点是较为公平偶然性较低但比赛过程往往十分冗长。本题中介绍的瑞士轮赛制因最早使用于 1895 年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中既保证了比赛的稳定性又能使赛程不至于过长。题目描述2 × N 2 \times N2×N名编号为1 ∼ 2 × N 1\sim 2\times N1∼2×N的选手共进行R RR轮比赛。每轮比赛开始前以及所有比赛结束后都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前的排名有关第1 11名和第2 22名、第3 33名和第4 44名、……、第 $2\times K - 1 $ 名和第2 × K 2\times K2×K名、…… 、第2 × N − 1 2\times N - 12×N−1名和第2 × N 2\times N2×N名各进行一场比赛。每场比赛胜者得1 11分负者得0 00分。也就是说除了首轮以外其它轮比赛的安排均不能事先确定而是要取决于选手在之前比赛中的表现。现给定每个选手的初始分数及其实力值试计算在R RR轮比赛过后排名第Q QQ的选手编号是多少。我们假设选手的实力值两两不同且每场比赛中实力值较高的总能获胜。输入格式第一行是三个正整数N , R , Q N,R,QN,R,Q每两个数之间用一个空格隔开表示有 $2\times N $ 名选手、R RR轮比赛以及我们关心的名次Q QQ。第二行是2 × N 2\times N2×N个非负整数s 1 , s 2 , … , s 2 × N s_1, s_2,\dots, s_{2\times N}s1​,s2​,…,s2×N​每两个数之间用一个空格隔开其中 $s_i $ 表示编号为i ii的选手的初始分数。第三行是2 × N 2\times N2×N个正整数w 1 , w 2 , … , w 2 × N w_1,w_2,\dots,w_{2\times N}w1​,w2​,…,w2×N​每两个数之间用一个空格隔开其中w i w_iwi​表示编号为i ii的选手的实力值。输出格式一个整数即R RR轮比赛结束后排名第Q QQ的选手的编号。输入输出样例 #1输入 #12 4 2 7 6 6 7 10 5 20 15输出 #11说明/提示【样例解释】【数据范围】对于30 % 30\%30%的数据1 ≤ N ≤ 100 1\le N\le 1001≤N≤100对于50 % 50\%50%的数据1 ≤ N ≤ 10000 1\le N\le 100001≤N≤10000对于100 % 100\%100%的数据1 ≤ N ≤ 10 5 , 1 ≤ R ≤ 50 , 1 ≤ Q ≤ 2 × N , 0 ≤ s 1 , s 2 , … , s 2 × N ≤ 10 8 , 1 ≤ w 1 , w 2 , … , w 2 × N ≤ 10 8 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^81≤N≤105,1≤R≤50,1≤Q≤2×N,0≤s1​,s2​,…,s2×N​≤108,1≤w1​,w2​,…,w2×N​≤108。noip2011 普及组第 3 题。解题思路本题核心是归并排序优化高效模拟瑞士轮赛制解决大数据量的排序瓶颈。共有2 N 2N2N名选手进行R RR轮比赛每轮按排名两两对决实力强者获胜加分。关键特性每轮比赛后的胜者组、败者组均保持有序因此无需每次都进行全量快速排序仅用归并操作合并两个有序数组即可完成排名更新将时间复杂度从O ( R N log ⁡ N ) O(RN\log N)O(RNlogN)优化至O ( R N ) O(RN)O(RN)。初始对选手排序后循环执行比赛计分、分离胜负组、归并排序最终直接输出第Q QQ名的选手编号完美适配题目大数据约束。总结核心逻辑利用胜负组天然有序的特性用归并排序替代全量排序极致优化效率。关键操作初始排序、两两对决计分、分离胜负数组、线性归并合并。效率保障归并排序无冗余运算轻松应对N ≤ 10 5 N \le 10^5N≤105、R ≤ 50 R \le 50R≤50的数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N2e510;constll INF1e18;constll M1e610;constll mod1e97;ll n,r,q;ll a[200100],win[200100],lose[200100];ll s[200100],w[200100];boolcmp(ll x,ll y){if(s[x]s[y])returnxy;returns[x]s[y];}voidmerge(){ll i,j;ij1,a[0]0;while(iwin[0]jlose[0])if(cmp(win[i],lose[j]))a[a[0]]win[i];elsea[a[0]]lose[j];while(iwin[0])a[a[0]]win[i];while(jlose[0])a[a[0]]lose[j];}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnrq;n*2;for(ll i1;in;i)a[i]i;for(ll i1;in;i)cins[i];for(ll i1;in;i)cinw[i];sort(a1,an1,cmp);for(ll i1;ir;i){win[0]lose[0]0;for(ll j1;jn;j2)if(w[a[j]]w[a[j1]]){s[a[j]];win[win[0]]a[j];lose[lose[0]]a[j1];}else{s[a[j1]];win[win[0]]a[j1];lose[lose[0]]a[j];}merge();}couta[q]endl;return0;}