Warning: session_start(): open(/tmp/sess_7ea1e656dbe937ad91ec06f838ea9016, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 一道让我有所收获的题（线性表的组织） ======
洛谷链接：https:%%//%%www.luogu.com.cn/problem/P1160
考察点：线性表的组织、插入删除与查找
===== 题目描述 =====
一个学校里老师要将班上N个同学排成一列，同学被编号为1∼N，他采取如下的方法：
- 先将1号同学安排进队列，这时队列中只有他一个人；
- 2−N号同学依次入列，编号为i的同学入列方式为：老师指定编号为i的同学站在编号为1∼(i−1)中某位同学（即之前已经入列的同学）的左边或右边；
- 从队列中去掉M(M
4
1 0
2 1
1 0
2
3
3
**输出**
2 4 1
===== 说明/提示 =====
==== 样例解释： ====
将同学2插入至同学1左边，此时队列为：21
将同学3插入至同学2右边，此时队列为：231
将同学4插入至同学1左边，此时队列为：2341
将同学3从队列中移出，此时队列为：241
同学3已经不在队列中，忽略最后一条指令
最终队列：241
==== 数据范围 ====
对于20%的数据，有N≤10；对于40%的数据，有N≤1000；对于100%的数据，有N,M≤100000。
===== 解题说明 =====
本题考查点为线性表。由于我们需要对题目进行按照要求采用双向链表进行操作即可。但是如果单纯的用链表会产生TLE等情况。这时想到数组具有查找快的特点，链表具有插入删除快的特点。同时注意到学生的顺序是依次连续增加的。所以可以将二者的优点结合起来，用结构体数组存链表。这样就解决了TLE的问题。
==== 参考代码 ====
#include
#include
struct Node {
int flag;
int id;
struct Node *left;
struct Node *right;
}queue[100010];
int main() {
struct Node *head;
head = &queue[0];
head->id = 1;
head->flag = 0;
head->left = NULL;
head->right = NULL;
int i;
int n;
scanf("%d", &n);
for (i = 2; i <= n; i++) {
int k, p;
struct Node *next = NULL;
next = &queue[i - 1];
scanf("%d%d", &k, &p);
struct Node *temp = &queue[k - 1];
if (p == 0) {
next->id = i;
next->flag = 0;
next->right = temp;
if (temp->left != NULL) {
next->left = temp->left;
temp->left->right = next;
}
else {
head = next;
}
temp->left = next;
}
else {
next->id = i;
next->flag = 0;
next->left = temp;
if (temp->right != NULL) {
next->right = temp->right;
temp->right->left = next;
}
temp->right = next;
}
}
int m;
scanf("%d", &m);
for (i = 0; i < m; i++) {
int temp;
scanf("%d", &temp);
queue[temp - 1].flag = 1;
}
struct Node *temp = head;
while (temp != NULL) {
if (temp->flag != 1) {
printf("%d ", temp->id);
}
temp = temp->right;
}
return 0;
}