每日一题-19th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

LuoGu P1160. 队列安排

题目描述

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

先将 $1$ 号同学安排进队列，这时队列中只有他一个人；
$2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；
从队列中去掉 $M$ 个同学，其他同学位置顺序不变。

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

说明

输入格式

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

第 $2\sim N$ 行，第 $i$ 行包含两个整数 $k,p$，其中 $k$ 为小于 $i$ 的正整数，$p$ 为 $0$ 或者 $1$。若 $p$ 为 $0$，则表示将 $i$ 号同学插入到 $k$ 号同学的左边，$p$ 为 $1$ 则表示插入到右边。

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

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

输出格式

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

样例 1 输入

样例 1 输出

2 4 1

样例 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\%$ 的数据，$1\leq N\leq 10$。

对于 $40\%$ 的数据，$1\leq N\leq 1000$。

对于 $100\%$ 的数据，$1<M\leq N\leq 10^5$。

思路和实现

一开始就认为链表解这题非常合适，所以手撸一个单链表类 SLinkedList（元素 int）：

#include <cstdio>
using namespace std;
struct node {
    int data;
    node* next;
    node(int dt=0, node* nxt=0)
        : data(dt), next(nxt) {}
};
struct SLinkedList {
    node* head;
    SLinkedList(int stu) { head = new node(0, new node(stu)); }
    ~SLinkedList() {}    // 追求速度
    void insert(int stu, int newStu, int right) {
        node* cur = head;
        while (cur->next) {
            if (cur->next->data == stu) {
                if (right) cur = cur->next;
                cur->next = new node(newStu, cur->next);
                return;
            }
            cur = cur->next;
        }
    }
    void traverse(bool* v) const {
        node* cur = head;
        while (cur->next) {
            cur = cur->next;
            if (v[cur->data])
                printf("%d ", cur->data);
        }
    }
};

int main() {
    SLinkedList slist(1);
    int n, m, stu, right; scanf("%d", &n);
    bool* v = new bool[n + 1];
    for (int i = 1; i <= n; ++i) v[i] = 1;
    for (int i = 2; i <= n; ++i) {
        scanf("%d%d", &stu, &right);
        slist.insert(stu, i, right);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &stu);
        v[stu] = 0;
    }
    slist.traverse(v);
    return 0;
}

真的很损，又是三个测试集超时🤬，这还要更快，，那就不能用普通的链表了（声明：本人从不使用 STL 做题）；

为了追求极致速度，用空间换时间，使用的链表在取用元素时，必须像顺序表一样快——好，就顺序表！但是又要找元素左边的元素，所以只能用数组模拟双链表；

#include<cstdio>
#include<cstring>
using namespace std;
#define MAXLEN 100001
int stus[MAXLEN][3];        // stu[i][1]:  第i人左边序号、stu[i][2]: 第i人右边序号
                            // stu[i][0]: 第i人是否在队中
void insert(int stu, int newStu, int right) {
    if (right) {
        int tmpR;
        if (tmpR = stus[stu][2]) {    // 插入右边，右边有人
            stus[tmpR][1] = newStu;
            stus[stu][2] = newStu;
            stus[newStu][1] = stu;
            stus[newStu][2] = tmpR;
        }
        else {    // 插入右边，右边没人
            stus[stu][2] = newStu;
            stus[newStu][1] = stu;
        }
    }
    else {
        int tmpL;
        if (tmpL = stus[stu][1]) {
            stus[tmpL][2] = newStu;
            stus[stu][1] = newStu;
            stus[newStu][1] = tmpL;
            stus[newStu][2] = stu;
        }
        else {
            stus[stu][1] = newStu;
            stus[newStu][2] = stu;
        }
    }
    stus[newStu][0] = 1;
}

void remove(int stu) {
    if (!(stus[stu][0])) return;
    int tmpL = stus[stu][1], tmpR = stus[stu][2];
    if (stus[tmpL][0] && stus[tmpR][0]) {
        stus[tmpL][2] = tmpR;
        stus[tmpR][1] = tmpL;
    }
    else if (stus[tmpL][0]) stus[tmpL][2] = 0;
    else if (stus[tmpR][0]) stus[tmpR][1] = 0;
    stus[stu][0] = stus[stu][1] = stus[stu][2] = 0;
}

void traverse() {
    int start = 1;
    while (start <= MAXLEN) {
        if (!(stus[start][1]) && stus[start][2]) break;
        ++start;
    }
    if (start <= MAXLEN) {
        while (stus[start][0]) {
            printf("%d ", start);
            start = stus[start][2];
        }
    }
}

int main() {
    int n, m, stu, right; scanf("%d", &n);
    memset(stus, 0, sizeof(stus));
    stus[1][0] = 1;
    for (int i = 2; i <= n; ++i) {
        scanf("%d%d", &stu, &right);
        insert(stu, i, right);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &stu);
        remove(stu);
    }
    traverse();
    return 0;
}