P1160 队列安排

题目原文及输入/输出格式

题目描述

一个学校里老师要将班上NN个同学排成一列，同学被编号为1∼N，他采取如下的方法：

1. 先将1号同学安排进队列，这时队列中只有他一个人；
2. 2~N号同学依次入列，编号为i的同学入列方式为：老师指定编号为i的同学站在编号为1~(i−1)中某位同学（即之前已经入列的同学）的左边或右边；
3. 从队列中去掉M(M<N)个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

思路

根据题目描述可以看出本题需要多次对队列进行插入以及删除操作，自然联想到使用链表。

40分解法

对于每个链表N内的元素node记录其上一个元素和下一个元素的下标和这个node代表的学生编号并使用cnt变量记录链表N内学生总数。每次更新总是在下标为cnt+1存入新的元素。

代码

struct node{
	int last, next, id;
	
	node(int last, int next, int id){
		this->id=id;
		this->next=next;
		this->last=last;
	}
	
	node(){}
	
}N[100010];

int n, m, cnt=0, head; 

void print(){
	int temp=head;
	while(N[temp].next!=0){
		cout<<N[temp].id<<" ";
		temp=N[temp].next;
	}
	cout<<N[temp].id;
}

int main()
{
	cin>>n;
	N[++cnt]=node(0, 0, 1);
	head=1;
	for(int i=2;i<=n;i++){
		int a,b,ans=-1;
		cin>>a>>b;
		int temp=head;
		while(N[temp].next!=0){
			if(N[temp].id==a){
				ans=temp;
				break;
			}
			temp=N[temp].next;
		}
		if(ans==-1) ans=temp;
		
		if(b==0){
			node newN=node(N[ans].last, ans, i);
			N[++cnt]=newN;
			int t1=N[ans].last, t2=ans;
			N[t2].last=cnt;
			N[t1].next=cnt;
			
			if(ans==head) head=cnt;
		}else{
			node newN=node(ans, N[ans].next, i);
			N[++cnt]=newN;
			int t1=ans, t2=N[ans].next;
			N[t2].last=cnt;
			N[t1].next=cnt;
		}
	}
	
	cin>>m;
	for(int i=1;i<=m;i++){
		int a, ans=-1;
		cin>>a;
		int temp=head;
		while(N[temp].next!=0){
			if(N[temp].id==a){
				ans=temp;
				break;
			}
			temp=N[temp].next;
		}
		if(ans==-1){
			if(N[temp].id==a){
				ans=temp;
			}
		}
		
		if(ans!=-1){
			int t1=N[ans].last;
			int t2=N[ans].next;
			N[t1].next=N[ans].next;
			N[t2].last=N[ans].last;
		}
	}
	print();
    return 0;
}

反思

每一次添加和删除都要遍历整个链表，每次遍历时间复杂度为$O(n)$，所以整个程序时间复杂度为$O(n^2)$。由于题目数据:对于100%的数据，有N, M≤100000(N,M≤100000)。所以必定TLE。

AC解法

将学生编号作为下标，省去了cnt变量和每次插入和删除时的修改步骤，使每次遍历的时间复杂度为$O(1)$，程序时间复杂度降到$O(n)$。

代码

struct node{
	int last, next;
	
	node(int last, int next){
		this->next=next;
		this->last=last;
	}
	
	node(){}
	
}N[100010];

int n, m, head, end; 

void print(){
	int temp=head;
	while(temp!=end){
		cout<<temp<<" ";
		temp=N[temp].next;
	}
	cout<<temp;
}

int main()
{
	cin>>n;
	head=1, end=1;
	N[head]=node(0, 0);
	for(int i=2;i<=n;i++){
		int a,b;
		cin>>a>>b;
		
		if(b==0){
			node newN=node(N[a].last, a);
			N[i]=newN;
			int t1=N[a].last, t2=a;
			N[t2].last=i;
			N[t1].next=i;
			
			if(a==head) head=i;
		}else{
			node newN=node(a, N[a].next);
			N[i]=newN;
			int t1=a, t2=N[a].next;
			N[t2].last=i;
			N[t1].next=i;
			
			if(a==end) end=i;
		}
	}
	
	cin>>m;
	for(int i=1;i<=m;i++){
		int a;
		cin>>a;
		
		if(N[a].last!=-1 && N[a].next!=-1){
			if(a==head) head=N[a].next;
			if(a==end) end=N[a].last;
			
			int t1=N[a].last;
			int t2=N[a].next;
			N[t1].next=N[a].next;
			N[t2].last=N[a].last;
			N[a].last=-1;
			N[a].next=-1;
		}
	}
	print();
    return 0;
}