?https://www.luogu.org/problem/show?pid=1160
題目描述
一個學校里老師要將班上N個同學排成一列,同學被編號為1~N,他采取如下的方法:
1.先將1號同學安排進隊列,這時隊列中只有他一個人;
2.2~N號同學依次入列,編號為i的同學入列方式為:老師指定編號為i的同學站在編號為1~i -1中某位同學(即之前已經入列的同學)的左邊或右邊;
雙端隊列的出隊順序圖。3.從隊列中去掉M(M<N)個同學,其他同學位置順序不變。
在所有同學按照上述方法隊列排列完畢后,老師想知道從左到右所有同學的編號。
輸入輸出格式
輸入格式:
?
組raid0,輸入文件arrange.in的第1行為一個正整數N,表示了有N個同學。
第2~第N行,第i行包含兩個整數k,p,其中k為小于i的正整數,p為0或者1。若p為0,則表示將i號同學插入到k號同學的左邊,p為1則表示插入到右邊。
第N+1行為一個正整數M,表示去掉的同學數目。
接下來M行,每行一個正整數x,表示將x號同學從隊列中移去,如果x號同學已經不在隊列中則忽略這一條指令。
?
輸出格式:
?
輸入文件arrange.out僅包括1行,包含最多N個空格隔開的正整數,表示了隊列從左到右所有同學的編號,行末換行且無空格。
?
輸入輸出樣例
4 1 0 2 1 1 0 2 3 3
2 4 1將同學2插入至同學1左邊,此時隊列為: 2 1 將同學3插入至同學2右邊,此時隊列為: 2 3 1 將同學4插入至同學1左邊,此時隊列為: 2 3 4 1 將同學3從隊列中移出,此時隊列為: 2 4 1 同學3已經不在隊列中,忽略最后一條指令 最終隊列: 2 4 1
說明
對于20%的數據,有N≤10;
對于40%的數據,有N≤1000;
對于100%的數據,有N, M≤100000。
1 #include <algorithm> 2 #include <iostream> 3 #define N 1000015 4 5 using namespace std; 6 7 int n,x,y,m; 8 struct node 9 { 10 int pre,next; 11 }que[N]; 12 13 int main() 14 { 15 cin>>n; 16 que[0].next=1; 17 que[1].pre=0,que[1].next=-1; 18 for(int i=2;i<=n;i++) 19 { 20 cin>>x>>y; 21 if(y) 22 { 23 que[que[x].next].pre=i; 24 que[i].next=que[x].next; 25 que[x].next=i; 26 que[i].pre=x; 27 } 28 else 29 { 30 que[i].pre=que[x].pre; 31 que[que[x].pre].next=i; 32 que[x].pre=i; 33 que[i].next=x; 34 } 35 } 36 37 cin>>m; 38 for(int i=1;i<=m;i++) 39 { 40 cin>>x; 41 if(que[x].next==-1&&que[x].pre==-1) continue; 42 que[que[x].pre].next=que[x].next; 43 que[que[x].next].pre=que[x].pre; 44 que[x].next=que[x].pre=-1; 45 } 46 int k=que[0].next; 47 while(k!=-1) 48 { 49 cout<<k<<" "; 50 k=que[k].next; 51 } 52 return 0; 53 }
1 #include <algorithm> 2 #include <iostream> 3 #define N 100005 4 5 using namespace std; 6 7 int n,m,x,y,z,top; 8 int que[N]; 9 int vis[N]; 10 11 int main() 12 { 13 cin>>n; 14 que[++top]=1; 15 for(int i=2;i<=n;i++) 16 { 17 cin>>x>>y; 18 if(y==0) 19 { 20 for(int j=1;j<=top;j++) 21 { 22 if(que[j]==x) 23 { 24 top++; 25 for(int k=top;k>j;k--) 26 que[k]=que[k-1]; 27 que[j]=i; 28 break; 29 } 30 } 31 } 32 else 33 { 34 for(int j=1;j<=top;j++) 35 { 36 if(que[j]==x) 37 { 38 top++; 39 for(int k=top;k>=j;k--) 40 que[k+1]=que[k]; 41 que[j+1]=i; 42 break; 43 } 44 } 45 } 46 } 47 cin>>m; 48 for(int i=1;i<=m;i++) 49 { 50 cin>>x; 51 vis[x]=1; 52 if(vis[x]) 53 for(int j=1;j<=top;j++) 54 { 55 if(que[j]==x) 56 { 57 for(int k=j;k<top;k++) 58 que[k]=que[k+1]; 59 top--; 60 break; 61 } 62 } 63 } 64 for(int i=1;i<=top;i++) 65 cout<<que[i]<<" "; 66 return 0; 67 }
?