80分双队列求优化
查看原帖
80分双队列求优化
1274368
YQD_Q楼主2024/4/3 12:45

TLE 6号点和8号点,大佬们求调

#include <bits/stdc++.h>
using namespace std;
queue <int> q1,q0;
int n,dot;

void cs(){
	cout<<endl<<"-----------------"<<endl;
	for(int i=1;i<=q0.size();i++){
		cout<<q0.front()<<' ';
		q0.push(q0.front());
		q0.pop();
	}
	cout<<endl;
	for(int i=1;i<=q1.size();i++){
		cout<<q1.front()<<' ';
		q1.push(q1.front());
		q1.pop();
	}
	cout<<endl<<"-----------------"<<endl;
}

void cz0(int dot){
	while(q0.front()<dot&&q0.front()!=-1){
		q0.push(q0.front());
		q0.pop();
	}
}
//这里的dot等价于dp 
void cz1(int dot){
	while(q1.front()<dot&&q1.front()!=-1){
		q1.push(q1.front());
		q1.pop();
	}
}

void c1(){
	while(q0.front()!=-1){
		q0.push(q0.front());
		q0.pop();
	}
	q0.pop();
	while(q1.front()!=-1){
		q1.push(q1.front());
		q1.pop();
	}
	q1.pop();
}

signed main(){
	cin>>n;
	for(int i=1,x=0;i<=n;i++){
		cin>>x;
		if(x==1) q1.push(i);
		else q0.push(i);
	}
	int dp=1;//dp指当前的所指向的数
	while(!q0.empty()&&!q1.empty()){
		if(q0.front()>q1.front()){
			dp=q1.front();
			cout<<dp<<' ';
			q1.pop();
			dot=0;//dot指向目前查看1号还是0号
		}
		else{
			dp=q0.front();
			cout<<dp<<' ';
			q0.pop();
			dot=1;
		}
		q1.push(-1);q0.push(-1);
		while(1){
			if(dot==0){
				cz0(dp);
				if(q0.front()==-1||q0.empty()) break;//退出机制 
//				cs();
				dot=1;
				dp=q0.front();
				cout<<dp<<" ";
				q0.pop();
			}
			else{
				cz1(dp);
				if(q1.front()==-1||q1.empty()) break;//退出机制 
//				cs();
				dot=0;
				dp=q1.front();
				cout<<dp<<" ";
				q1.pop();
			}
		}
		c1();
		cout<<endl;
	//	cs();
	}
	while(!q0.empty()){
		cout<<q0.front()<<' '<<endl;
		q0.pop();
	}
	while(!q1.empty()){
		cout<<q1.front()<<' '<<endl;
		q1.pop();
	}
}
2024/4/3 12:45
加载中...