2025.2.12总结

队列：

题目描述

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

1. 先将 11 号同学安排进队列，这时队列中只有他一个人；

2. 2∼𝑁2∼N 号同学依次入列，编号为 𝑖i 的同学入列方式为：老师指定编号为 𝑖i 的同学站在编号为 1∼(𝑖−1)1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 𝑀M 个同学，其他同学位置顺序不变。

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

输入格式

第一行一个整数 𝑁N，表示了有 𝑁N 个同学。

第 2∼𝑁2∼N 行，第 𝑖i 行包含两个整数 𝑘,𝑝k,p，其中 𝑘k 为小于 𝑖i 的正整数，𝑝p 为 00 或者 11。若 𝑝p 为 00，则表示将 𝑖i 号同学插入到 𝑘k 号同学的左边，𝑝p 为 11 则表示插入到右边。

第 𝑁+1N+1 行为一个整数 𝑀M，表示去掉的同学数目。

接下来 𝑀M 行，每行一个正整数 𝑥x，表示将 𝑥x 号同学从队列中移去，如果 𝑥x 号同学已经不在队列中则忽略这一条指令。

输出格式

一行，包含最多 𝑁N 个空格隔开的整数，表示了队列从左到右所有同学的编号。

输入输出样例

输入 #1复制

4
1 0
2 1
1 0
2
3
3

输出 #1复制

2 4 1

代码： 

#include <stdio.h>int main()
{int N,k,p,M,x;scanf("%d",&N);int arr[N];int size=0;arr[size++]=1;for(int i = 2; i <= N; i++){scanf("%d %d",&k,&p);int pos=-1;for (int j = 0; j < size; j++){if(arr[j] == k){pos=j;break;}}if(p == 0){for(int j = size; j > pos; j--){arr[j]=arr[j - 1];}arr[pos] = i;}else{for(int j = size; j > pos + 1; j--){arr[j]=arr[j - 1];}arr[pos + 1] = i;}size++;}scanf("%d",&M);int removed[N + 1];for(int i = 0; i <= N; i++){removed[i]=0;}for (int i = 0; i < M; i++){scanf("%d",&x);removed[x]=1;}int output_count=0;for(int i = 0; i < size; i++){if(!removed[arr[i]]){if(output_count>0){printf(" ");}printf("%d",arr[i]);output_count++;}}printf("\n");return 0;
}