为什么啊啊啊!我我明明计算时间复杂度是R*(log n + n)。答案2、8、9、10却是time limit exceeded.
求助大神
#include<bits/stdc++.h>
using namespace std;
struct Player{
int hao,fen,li;
//用结构体记录编号、分数、实力
};
Player p[200010];
Player pt[200010];//建立临时数组
int n,r,q;
bool cmp(Player p1,Player p2){
if(p1.fen==p2.fen)
return p1.hao<p2.hao;
return p1.fen>p2.fen;
}
void pai(){
int a=1,b=2,t=1;//a是比赛中胜者,b是比赛的败者,c是临时pt的下标
while(a<=2*n || b<=2*n){
if((p[a].fen>p[b].fen)||((p[a].fen==p[b].fen)&&(p[a].hao<p[b].hao))){
pt[t]=p[a];
a+=2;
}
else if((p[a].fen<p[b].fen)||((p[a].fen==p[b].fen)&&(p[a].hao>p[b].hao))){
pt[t]=p[b];
b+=2;
}
t++;
}
while(b<=2*n){
pt[t]=p[b];
b+=2;
t++;
}
while(a<=2*n){
pt[t]=p[a];
a+=2;
t++;
}
for(int i=1;i<=2*n;i++){
p[i]=pt[i];
}
}
int main(){
//完成输入
cin>>n>>r>>q;
for(int i=1;i<=2*n;i++){
cin>>p[i].fen;
p[i].hao=i;
}
for(int i=1;i<=2*n;i++){
cin>>p[i].li;
}
//进行一次快排
sort(p+1,p+2*n+1,cmp);
//开始模拟比赛
while(r){
//比赛现场
for(int i=1;i<=2*n;i+=2){
if(p[i].li>p[i+1].li)
p[i].fen++;
else{
p[i+1].fen++;
Player tt;
tt=p[i];p[i]=p[i+1];p[i+1]=tt;
}
}
//排名现场
pai();
r--;
}
cout<<p[q].hao;
return 0;
}