P7912

测试点记录

#include<bits/stdc++.h>
using namespace std;
deque<int>q[100005];//建立队列，记录每个“块” 
int fx[100005],fy[100005];//fx记录指向fx[i]的队列，fy记录fy[i]指向的队列 
int n,a,l=1,x;//l记录有多少个块 
int main()
{
	scanf("%d\n",&n);
	scanf("%d",&x);
	a=x;
	q[1].push_back(1);
    fx[1]=0,fy[0]=1;
	for(int i=2;i<=n;i++)
	{
		scanf(" %d",&x);
		if(x==a)//分块 
		{
			q[l].push_back(i);
			fx[l]=l-1,fy[l-1]=l;
		}
		else
		{
			l++,a=x;
			q[l].push_back(i);
			fx[l]=l-1,fy[l-1]=l;
		}
	}
	fy[l]=l+1;
	while(true)
	{
		bool sc=false;
		for(int i=fy[0];i<=l;i=fy[i])
		{
			if(sc==false)
			{
				a=q[i].front();
			    printf("%d ",q[i].front());
			    q[i].pop_front();
			    if(q[i].empty())//队列为空 
			    {
				    fy[fx[i]]=fy[i];
				    fx[fy[i]]=fx[i];
			    }
			    sc=true;
		    }
		    else if(q[i].front()!=a)
		    {
				a=q[i].front();
			    printf("%d ",q[i].front());
			    q[i].pop_front();
			    if(q[i].empty())
			    {
				    fy[fx[i]]=fy[i];
				    fx[fy[i]]=fx[i];
			    }
			}
		}
		if(sc==false)break;//没有输出，所有队列为空 
		printf("\n");
	}
	return 0;
}