P1160 队列安排（list vector 链表）

题的链接： 点击这里：P1160 队列安排

题解： 介意看1.0和3.0，其他两个。。。。

参考代码1.0： 结构体数组实现（模拟链表）

注意：

初始化第一个同学前后都没有人插入时，将当前人物的前后分别指向要插入k的前后，再将k前的人的next改到当前人数i,将k后的人pre指向i，右操作类似； L[i].pre = L[K].pre; L[i].next = K; L[L[K].pre].next = i; L[K].pre = i; 删除时，先判断删没删过，没删过则开始删，即修改删除元素前后元素的指向，删除掉后，将删除元素前后都置为-1，表示已经删除。 L[L[X].pre].next = L[X].next; L[L[X].next].pre = L[X].pre; L[X].pre = L[X].next = -1; 从链表头输出时，需要找到表头，即该元素的pre为0的那个，找到后，输出，同时让pos = L[pos].next 。删除元素的pre和next都等于-1 。 #include <queue> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f #define MAX 5010 using namespace std; typedef struct Node { int pre, next; }List; List L[100010]; int N, k, p, M, x; void InitList() { L[1].next = L[1].pre = 0; } void InsertList(int i, int K, int P) { if(P == 0)//左 { L[i].pre = L[K].pre; L[i].next = K; L[L[K].pre].next = i; L[K].pre = i; } else//右 { L[i].pre = K; L[i].next = L[K].next; L[L[K].next].pre = i; L[K].next = i; } } void DeleteList(int X) { if(L[X].pre == -1 && L[X].next == -1) return; L[L[X].pre].next = L[X].next; L[L[X].next].pre = L[X].pre; L[X].pre = L[X].next = -1; } void PrintList() { int pos; for(int i = 1; i <= N; i++) if(L[i].pre == 0) {pos = i; break;} while(pos > 0) { cout << pos <<" "; pos = L[pos].next; } } int main() { cin >> N; InitList(); for(int i = 2; i <= N; i++) { cin >> k >> p; InsertList(i, k, p); } cin >> M; for(int i = 0; i < M; i++) { cin >> x; DeleteList(x); } PrintList(); return 0; }

参考代码2.0： 结构体指针实现（双向链表），用vis来标记是否已经删过，删过则直接return，但是仅仅能通过前连个测试点，后面都超时（原因： 应该是每次在插入和删除时都要一个个循环来找位置，浪费大量时间，建议用代码1.0，数组实现时在查找和删除时都是O(1)的），（结论：数据量大的时候，链表最好用数组实现）

#include <queue> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f #define MAX 5010 using namespace std; typedef struct Node { int data; Node *pre, *next; }*List; int N, k, p, M, x; bool vis[10010]; List InitList() { List L, head; L = (List)malloc(sizeof(Node)); L->pre = L->next = NULL; head = (List)malloc(sizeof(Node)); head->data = 1; head->next = L->next; if(L->next != NULL) L->next->pre = head; L->next = head; head->pre = L; return L; } void InsertList(List L, int i, int K, int P) { List t = L->next; List s = (List)malloc(sizeof(Node)); s->data = i; while(t->data != K && t != NULL) { t = t->next; } if(t == NULL) return; if(P == 0) t = t->pre; s->next = t->next; if(t->next != NULL) t->next->pre = s; s->pre = t; t->next = s; } void DeleteList(List L, int X)//2 3 4 1 { if(vis[X]) return; vis[X] = true; List t = L->next; List s; int i = 0; while(t->data != X && t != NULL) { t = t->next; } if(t == NULL) return; s = t->pre; s->next = t->next; if(t->next != NULL) t->next->pre = s; free(t); } void PrintList(List L) { List t = L->next; while(t != NULL) { cout << t->data <<" "; t = t->next; } cout << endl; } int main() { cin >> N; List L = InitList(); for(int i = 2; i <= N; i++) { cin >> k >> p; InsertList(L, i, k, p); } cin >> M; for(int i = 0; i < M; i++) { cin >> x; DeleteList(L, x); } PrintList(L); return 0; }

参考代码3.0： STL的list实现，用迭代器数组指向每个元素的迭代器，插入左边可以直接用insert函数，调用pos[k]，并将插入元素的迭代器返回到pos[i]；插入右边要先找到k的下一个迭代器，可以用next（）函数找到下一个迭代器，再插入，并将插入元素的迭代器返回到pos[i]；删除也可以直接调用erase函数，参数为删除元素的迭代器；用vis数组标记是否删除过；遍历直接用迭代器遍历就可以；

注意：

关于STL的list,点击这里！可以用next 和 prev来访问前后迭代器，点击这里了解！insert和erase函数都是返回迭代器； #include <list> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f #define MAX 5010 using namespace std; list<int>::iterator pos[100010]; //pos[x] 表示x的迭代器 list<int> L; bool vis[100010]; int N, k, p, M, x; int main() { cin >> N; L.push_front(1); //默认1迭代器地址为begin pos[1] = L.begin(); for(int i = 2; i <= N; i++) { cin >> k >> p; //insert返回值也为迭代器 if(p == 0) pos[i] = L.insert(pos[k], i); else { //或者 auto nex = next(pos[k]); //往k的右边插入，要找到k的下一个迭代器，用next查找 list<int>::iterator nex = next(pos[k]); pos[i] = L.insert(nex, i); } } cin >> M; for(int i = 0; i < M; i++) { cin >> x; if(!vis[x]) L.erase(pos[x]), vis[x] = true; } for(list<int>::iterator it = L.begin(); it != L.end(); it++) cout << *it <<" "; //或者 for(auto X : L) cout << X <<" "; return 0; }

参考代码4.0： STL的vector实现，会超时，应该可以写的和list一样也行，但是内存又会出问题，所以用find函数来找，但是仍然超时，省去删除操作，也会超时。。。；

#include <vector> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f #define MAX 5010 using namespace std; vector<int> v; bool vis[100010]; int N, k, p, M, x; int main() { cin >> N; v.push_back(1); pos[1] = v.begin(); for(int i = 2; i <= N; i++) { cin >> k >> p; if(p == 0) v.insert(find(v.begin(), v.end(), k), i); else v.insert(find(v.begin(), v.end(), k) + 1, i); } cin >> M; // for(int i = 0; i < M; i++) // { // cin >> x; // if(!vis[x]) v.erase(pos[x]), vis[x] = true; // } for(int i = 0; i < M; i++) { cin >> x;vis[x] = true; } for(vector<int>::iterator it = v.begin(); it != v.end(); it++) if(!vis[*it]) cout << *it <<" "; //for(auto X : v) cout << X <<" "; return 0; }