一般解法：先排序一次，然后重复r次：两两比较，把赢的人得分+1，最后排序。 代码： 时间复杂度：O(nlogn * r) (实际上n代表2n，但常数项省略) 最高运行时间：700ms左右✔（由于数组重复元素较多所以建议用stable_sort可以控制在600ms以下） 但是你放进洛谷里测:怎么两个TLE啊啊啊啊啊啊谁设的500ms啊啊啊啊啊啊啊 有没有优化的方法？？？ 答案是肯定的！！！ 我们仔细思考🤔：首先这个序列排序后得分是有序的，如果按顺序把赢了的和输了的分开是不是也是有序的？ 举个例子： 是不是有序的？ 如果你怀疑的话，你可以多实验几次（ 然后我们把赢了的队员全部加1分（实际上在进行分输赢时就可以加），由于加的数值是相同的，所以就算加一亿分都是有序（不考虑爆int） 知道了这个，接着怎么做？ 归并排序学过吗？ 没学过也不用担心！网上搜 其中最终要的一步之一好吧本身也就只有两步就是“并” 所谓并，就是把两个有序数组合并成一个 具体过程：把最前面的元素进行比较，哪个小（大）就拿哪个，然后进行下一轮比较 懂了吗？本来归并排序还有归的操作，是为了原来的无序数组要划分成无数个有序数组来合并 但是——因为只有两个有序数组需要排序，所以省去了很多小并，只剩下了一个大并（ 一次大并的时间复杂度为O(n)，按照题目重复r次，所以本题解时间复杂度就为O(n * r)了 废话不多说，下↓ 时间复杂度:O(n * r) 最高运行时间:147ms😎 不要CV球球了啊啊啊啊啊主要了解思路 看到了点个赞呗，第一次写这么长的题解qwq

#include<bits/stdc++.h> using namespace std; int n, r, q; struct node{ int x; int y; int z; }a[10000001]; node b[3000000],c[3000000]; bool cmp(node a, node b){ if(a.x!=b.x) return a.x>b.x; else return a.z<b.z; } int main(){ scanf("%d%d%d",&n,&r,&q); n*=2; for(int i=1;i<=n;i++) scanf("%d",&a[i].x); for(int i=1;i<=n;i++) scanf("%d",&a[i].y),a[i].z=i; sort(a+1,a+1+n,cmp); for(int i=1;i<=r;i++){ int i2=0, j2=0; for(int i=2;i<=n;i+=2) if(a[i].y>a[i-1].y)a[i].x++,b[++i2]=a[i],c[j2]=a[i-1]; else a[i-1].x,b[++i2]=a[i-1],c[++j2]=a[i]; merge(b+1,b+1+i2,c+1,c+1+j2,a+1,cmp); } printf("%d",a[q].z); return 0; }

题目意思:给你两个数组w和s，要求每次第一名(a[1])和第二(a[2])、第三和第四、第五和第六、第i(i+1<=n)和i+1名比赛,如果a[i].w>a[i+1].w则a[i].s++，然后重新按照a[i].s排序,重复以上操作直到操作次数等于R为止。求此时的A[Q].id 不难想到暴力算法,先把a排序,然后顺序扫描整个a如果a[i].w>a[i+1].w则a[i].s++,然后再快排一次。 时间复杂度为O(R*(2n)log2(2n))对于本题n<=100000,R<=50的规模 运算次数为5020000018=1.8亿次，会超时。 正解,设一个数组Win存储这一轮赢了的人,Lose存储输的。 依然是顺序扫描a,把赢了的人放入Win中,输了的放入Lose中。 然后把Win和Lose按照cmp来合并,合并后的数组就是新的a，更新a，继续下一次归并排序直到次数等于R,输出答案； 这种做法由于是直接合并,扫描是O(2n)的,所以最后的时间复杂度是O(R2n）就可以过了。 AC代码

每组比赛的胜者：赛前，总分是按降序排的；获胜后都得 111 分，仍是降序； 每组比赛的负者：赛前，总分是按降序排的；不得分，仍是降序。 先按初始分数排序，然后按分数高低两人一组比赛； 胜者入队 AAA ，负者入队 BBB 。这样 AAA 、 BBB 自身仍是有序的； 只需进行合并操作即可，合并操作的复杂度是 OOO ( nnn ),而如果用快排其复杂度为 OOO ( nlognnlognnlogn )

#include <bits/stdc++.h> using namespace std; struct dd1{ int name,pe,bh; }n[200001]; bool cmp(dd1 x,dd1 y){ if(x.name==y.name)return x.bh<y.bh; return x.name>y.name; } int main() { int a,b,c; cin>>a>>b>>c; a*=2; for(int i=1;i<=a;i++){ cin>>n[i].name; n[i].bh=i; } for(int i=1;i<=a;i++){ cin>>n[i].pe; } stable_sort(n+1,n+a+1,cmp); for(int j=1;j<=b;j++){ for(int i=1;i<=a-1;i+=2){ if(n[i].pe>n[i+1].pe)n[i].name++; else{ n[i+1].name++; } } stable_sort(n+1,n+a+1,cmp); } cout<<n[c].bh;

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,r,q; struct player{ int idx,score,iq; }a[2N],winner[N],loser[N]; bool cmp(player x,player y){ if(x.score!=y.score) return x.score>y.score; return x.idx<y.idx; } int main(){ cin>>n>>r>>q; for(int i=1;i<=2n;i++){ cin>>a[i].score; a[i].idx=i; } for(int i=1;i<=2n;i++){ cin>>a[i].iq; } sort(a+1,a+n2+1,cmp); while(r--){ int i1=1,i2=1; for(int i=1;i<=2*n;i+=2){ if(a[i].iq>a[i+1].iq){ a[i].score++; winner[i1++]=a[i]; loser[i2++]=a[i+1]; }else{ a[i+1].score++; winner[i1++]=a[i+1]; loser[i2++]=a[i]; } } int i=1,j=1; int idx=1; while(i<=n&&j<=n){ if(cmp(winner[i],loser[j])){ a[idx++]=winner[i++]; }else{ a[idx++]=loser[j++]; } } while(i<=n){ a[idx++]=winner[i++]; } while(j<=n){ a[idx++]=loser[j++]; } } cout<<a[q].idx; return 0; }

#include<bits/stdc++.h> using namespace std; struct Player{ int id; int score; int power; }arr[1000002]; bool cmp(Player a,Player b){ if(a.score==b.score){ return a.id<b.id; } return a.score>b.score; } int main(){ int n,r,q; cin>>n>>r>>q; for(int i=1;i<=2n;i++){ cin>>arr[i].score; arr[i].id=i; } for(int i=1;i<=2n;i++){ cin>>arr[i].power; } sort(arr+1,arr+1+2n,cmp); for(int i=1;i<=r;i++){ for(int j=1;j<=2n;j+=2){ if(arr[j].power>arr[j+1].power){ arr[j].score+=1; }else{ arr[j+1].score+=1; } } sort(arr+1,arr+1+2*n,cmp); } cout<<arr[q].id; return 0; }

#include<bits/stdc++.h> using namespace std; struct Player{ int id; int score; int power; }arr[1000002]; bool cmp(Player a,Player b){ if(a.score==b.score){ return a.id<b.id; } return a.score>b.score; } int main(){ int n,r,q; cin>>n>>r>>q; for(int i=1;i<=2n;i++){ cin>>arr[i].score; arr[i].id=i; } for(int i=1;i<=2n;i++){ cin>>arr[i].power; } sort(arr+1,arr+1+2n,cmp); for(int i=1;i<=r;i++){ for(int j=1;j<=2n;j+=2){ if(arr[j].power>arr[j+1].power){ arr[j].score+=1; }else{ arr[j+1].score+=1; } } sort(arr+1,arr+1+2*n,cmp); } cout<<arr[q].id; return 0; }

#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5+10; struct node{ int id; int s; int w; }a[MAXN]; bool cmp(node a,node b) { if(a.**.s) return a.id<b.id; return a.***.s; } int main() { int n,r,q; queue<node> win,lose; cin>>n>>r>>q; n*=2; int cnt; node win_0,lose_0; for(int i=1;i<=n;++i) { cin>>a[i].s; a[i].id=i; } for(int i=1;i<=n;i) { cin>>a[i].w; } sort(a+1,a+n+1,cmp); for(int i=1;i<=r;i) { for(int j=1;j<=n-1;j+=2) { if(a[j].w>a[j+1].w) { a[j].s; win.push(a[j]); lose.push(a[j+1]); } else { a[j+1].s; win.push(a[j+1]); lose.push(a[j]); } } cnt=0; while(!win.empty() && !lose.empty()) { win_0=win.front(); lose_0=lose.front(); if(win_0.s>lose_0.s || (win_0.slose_0.s && win_0.id<lose_0.id)) { cnt++; a[cnt]=win.front(); win.pop(); } else{ cnt++; a[cnt]=lose.front(); lose.pop(); } } while(!win.empty()) { cnt++; a[cnt]=win.front(); win.pop(); } while(!lose.empty()) { cnt++; a[cnt]=lose.front(); lose.pop(); } } cout<<a[q].id; return 0; }

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+10; struct player{ ll s,w; int id; }a[N]; ll n,r,q; bool cmp(player x,player y){ if(x.s!=y.s) return x.s>y.s; return x.id<y.id; } int main(){ cin>>n>>r>>q; for(int i=1;i<=2n;i++){ cin>>a[i].s; a[i].id=i; } for(int i=1;i<=2n;i++){ cin>>a[i].w; } sort(a+1,a+2n+1,cmp); for(int i=1;i<=r;i++){ for(int j=1;j<=2n;j+=2){ if(a[j].w>a[j+1].w){ a[j].s++; }else{ a[j+1].s++; } } sort(a+1,a+2*n+1,cmp); } cout<<a[q].id; return 0; }