为什么tle啊?时间啊是时间啊
查看原帖
为什么tle啊?时间啊是时间啊
529016
lg1995楼主2021/6/14 21:53
为什么啊啊啊!我我明明计算时间复杂度是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;
}
2021/6/14 21:53
加载中...