为什么啊啊啊!我我明明计算时间复杂度是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;
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;
}