军训排队

题目

by 郑凯俐

描述

教官发指令让学生排队. 首先队首定为 0, 教官先入队 (为 1). 教官将会发出三种指令:

  • 1 x y: 编号 y 于编号 x 的后面入队;
  • 2 x: 编号 x 报告其后面人的编号, 队尾报告 0;
  • 3 x: 编号 x 出队.

最后所有人报告编号. 请输出这些报告.

提示: 编号小于 \(100000\), 指令数小于 \(200000\).

IO格式

输入:

指令数
第1条指令
...

输出:

所有报告

样例

输入:

7
1 1 2
1 1 3
2 3
1 2 4
3 1
1 0 5
2 4

输出:

2
0
5
3
2
4

解答

思路

这是一道很简单的模拟题, 不过对于时间复杂度要求比较高. 这里, 我们理论上应当使用链表; 但也可以采取数组模拟的链表.

这里, 我们以数组的下标直接作为编号, 这样就可以以 \(O(1)\) 的速度获取一个队伍位置, 从而快速求解.

代码

#include <cstdio>
using namespace std;

constexpr int NumMax = 100000;
constexpr int NMax = 200000;
constexpr int HeadNum = 0;   // 队首
constexpr int FirstNum = 1;  // 教官编号

struct Line {
    struct LineNode {
        LineNode() : prev(0), next(0){};

        int prev;
        int next;
    };

    Line(int _num) {
        nodes[HeadNum].prev = _num;
        nodes[HeadNum].next = _num;
    };

    LineNode nodes[NumMax];

    void insert(int, int);
    int report(int);
    void remove(int);
    void print();
};

void Line::insert(int prevnum, int target) {
    auto& prev = nodes[prevnum];
    auto& cur = nodes[target];
    auto& next = nodes[prev.next];
    auto nextnum = prev.next;
    cur.prev = prevnum;
    cur.next = nextnum;
    prev.next = target;
    next.prev = target;
}

int Line::report(int prevnum) { return nodes[prevnum].next; }

void Line::remove(int target) {
    auto& cur = nodes[target];
    auto prevnum = cur.prev, nextnum = cur.next;
    auto& prev = nodes[prevnum];
    auto& next = nodes[nextnum];
    cur.prev = 0;
    cur.next = 0;
    prev.next = nextnum;
    next.prev = prevnum;
}

void Line::print() {
    auto cur = HeadNum;
    while (nodes[cur].next != HeadNum) {
        cur = nodes[cur].next;
        printf("%d\n", cur);
    }
}

int main() {
    Line line(FirstNum);
    int N;
    scanf("%d", &N);
    for (auto i = 0; i < N; i++) {
        int cmd;
        scanf("%d", &cmd);
        switch (cmd) {
            case 1: {
                int x, y;
                scanf("%d%d", &x, &y);
                line.insert(x, y);
            } break;
            case 2: {
                int x;
                scanf("%d", &x);
                printf("%d\n", line.report(x));
            } break;
            case 3: {
                int x;
                scanf("%d", &x);
                line.remove(x);
            } break;
            default:
                break;
        }
    }
    line.print();
    return 0;
}

时空消耗

1	Accepted	0 ms	1540 KB
2	Accepted	0 ms	1536 KB
3	Accepted	0 ms	1540 KB
4	Accepted	0 ms	1540 KB
5	Accepted	0 ms	1536 KB
6	Accepted	0 ms	1544 KB
7	Accepted	4 ms	1540 KB
8	Accepted	28 ms	1536 KB
9	Accepted	40 ms	1540 KB
10	Accepted	60 ms	1540 KB