题目链接：https://www.luogu.org/problemnew/show/P1309
题解：
每次比赛前，每个人都是按照分数降序排好的，那么比赛完后，将选手按输赢分成两组，顺序依然按照原顺序，那么显然组内的分数依然是降序的。只要将两个组重新 $O(n)$ 合并即可。
这种合并类似于归并排序里的merge操作。
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+5; int n,r,q; struct P{ int id; ll w,s; bool operator>(const P& oth)const { if(s==oth.s) return id<oth.id; return s>oth.s; } }p[maxn],win[maxn],los[maxn]; int wsz,lsz; void print() { for(int i=1;i<=2*n;i++) printf("%d: %I64d %I64d\n",p[i].id,p[i].s,p[i].w); cout<<endl; } int main() { ios::sync_with_stdio(0); cin>>n>>r>>q; for(int i=1;i<=2*n;i++) p[i].id=i; for(int i=1;i<=2*n;i++) cin>>p[i].s; for(int i=1;i<=2*n;i++) cin>>p[i].w; sort(p+1,p+2*n+1,greater<P>{}); while(r--) { wsz=lsz=0; for(int i=1;i<=2*n;i+=2) { if(p[i].w>p[i+1].w) { p[i].s++; win[wsz++]=p[i]; los[lsz++]=p[i+1]; } else { p[i+1].s++; win[wsz++]=p[i+1]; los[lsz++]=p[i]; } } int i=0,j=0,k=1; while(i<wsz && j<=lsz) { if(win[i]>los[j]) p[k++]=win[i++]; else p[k++]=los[j++]; } while(i<wsz) p[k++]=win[i++]; while(j<lsz) p[k++]=los[j++]; } cout<<p[q].id<<endl; }
原文：https://www.cnblogs.com/dilthey/p/10454098.html