一个学校里老师要将班上NN个同学排成一列，同学被编号为1\sim N1∼N，他采取如下的方法：
先将11号同学安排进队列，这时队列中只有他一个人；
2-N2−N号同学依次入列，编号为i的同学入列方式为：老师指定编号为i的同学站在编号为1\sim (i -1)1∼(i−1)中某位同学（即之前已经入列的同学）的左边或右边；
从队列中去掉M(M<N)M(M<N)个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
第11行为一个正整数NN，表示了有NN个同学。
第2-N2−N行，第ii行包含两个整数k,pk,p，其中kk为小于ii的正整数，pp为00或者11。若pp为00，则表示将ii号同学插入到kk号同学的左边，pp为11则表示插入到右边。
第N+1N+1行为一个正整数MM，表示去掉的同学数目。
接下来MM行，每行一个正整数xx，表示将xx号同学从队列中移去，如果xx号同学已经不在队列中则忽略这一条指令。
11行，包含最多NN个空格隔开的正整数，表示了队列从左到右所有同学的编号，行末换行且无空格。
4 1 0 2 1 1 0 2 3 3
2 4 1
样例解释：
将同学22插入至同学11左边，此时队列为：
2 121
将同学33插入至同学22右边，此时队列为：
2 3 1231
将同学44插入至同学11左边，此时队列为：
2 3 4 12341
将同学33从队列中移出，此时队列为：
2 4 1241
同学33已经不在队列中，忽略最后一条指令
最终队列：
2 4 1241
数据范围
对于20\%20%的数据，有N≤10N≤10；
对于40\%40%的数据，有N≤1000N≤1000；
对于100\%100%的数据，有N, M≤100000N,M≤100000。
代码：
1 #include <cstdio> 2 #include <list> 3 4 using namespace std; 5 bool vis[100003]; 6 list<int> stus; 7 list<int>::iterator pos[100003]; 8 9 int main() 10 { 11 int n; 12 scanf("%d",&n); 13 stus.push_back(1); 14 pos[1] = stus.begin(); 15 for (int i=2;i<=n;i++) 16 { 17 int k,p; 18 scanf("%d%d",&k,&p); 19 if (p == 0) 20 { 21 pos[i] = stus.insert(pos[k],i); 22 } 23 else { 24 list<int>::iterator it = pos[k]; 25 ++it; 26 pos[i] = stus.insert(it,i); 27 } 28 29 } 30 int m = 0; 31 scanf("%d",&m); 32 for (int i=0;i<m;i++){ 33 int x; 34 scanf("%d",&x); 35 if (!vis[x]){ 36 stus.erase(pos[x]); 37 vis[x] = true; 38 } 39 } 40 for (list<int>::iterator i = stus.begin(); i != stus.end();i++) 41 { 42 printf("%d ",*i); 43 } 44 return 0; 45 }
几点说明，为了遍历列表方便，使用一个pos的迭代器数组来存放队列的迭代器；insert（）函数的两个参数（迭代器和值），将值插入在迭代器的左边，并且返回一个迭代器指向此时i的位置；如果想要实现插入对应数值的右边，将迭代器加一再插入在它的左边；
vis[]数组储存队列i处是否有数值，这样可以快速遍历队列；最后，使用迭代器遍历队列的时候，不能时迭代器等于队列的最后，否则越界。
原文：https://www.cnblogs.com/nowonder/p/list.html