P1160 队列安排

题目简述

将N个同学依次插入队伍中，再删除m个同学，求最终的队伍顺序

思路

这题是个很好的练习链表的题目，要注意的是在链表的头和尾要搞一个Head和Tail指针，不然超出边界会出错

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int Map[N];
struct Node{
  int id;
  struct Node *head;
  struct Node *next;
}s[N];
int main(){
  int n;
  cin>>n;
  for(int i=0;i<=n;i++){
  	s[i].id=i;
  	s[i].head=NULL;
  	s[i].next=NULL;
  }
  struct Node *Head=&s[1];
  struct Node *Next=&s[1];
  for(int i=2;i<=n;i++){
    int k,p;
    cin>>k>>p;
    switch(p){
      case 0:{
      	struct Node *x=&s[k];
      	struct Node *y=&s[i];
        if((Head->id)==k){
        	x->head=y;
        	y->next=x;
        	Head=y;
		}
		else {
			y->next=x;
			y->head=x->head;
			x->head=y;
			y->head->next=y;
		}
        break;
      }
      case 1:{
        struct Node *x=&s[k];
      	struct Node *y=&s[i];
        if((Next->id)==k){
        	x->next=y;
        	y->head=x;
        	Next=y;
		}
		else {
			y->head=x;
			y->next=x->next;
			x->next=y;
			y->next->head=y;
		}
        break;
      }
    }
  }
  int m;
  cin>>m;
  while(m--){
  	int p;
  	cin>>p;
  	if(Map[p])continue;
  	Map[p]=1;
  	if(Head->id==p)Head=Head->next;
  		else {
  			if(Next->id==p){
  				s[p].head->next=s[p].next;	
  				Next=Next->head;
			}
			else {
				s[p].head->next=s[p].next;	
				s[p].next->head=s[p].head;
			}
		}
  }
  while(Head!=NULL){
  	cout<<Head->id<<' ';
  	Head=Head->next;
  }
  return 0;
}