P1160. 队列安排

发表于 分类于 阅读次数： Waline： 本文字数： 416 阅读时长 ≈ 1 分钟

考点

  • 模拟
  • 链表

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e5 + 10;

struct Node
{
    int pre_, nxt_, key_;
    Node(int pre = 0, int nxt = 0, int key = 0) : pre_(pre), nxt_(nxt), key_(key) {}
} arr[LEN];

#define dummyhead arr[0]
int tot = 0, idx[LEN];

//找x的下标，若无则返回0(即伪节点)
int find(int x)
{
    int now = dummyhead.nxt_;
    while (now && arr[now].key_ != x)
        now = arr[now].nxt_;
    return now;
}

//y插到x的右边(后面)
void ins_back(int x, int y)
{
    // int now = find(x);
    int now = idx[x];
    arr[++tot] = Node(now, arr[now].nxt_, y);
    arr[arr[now].nxt_].pre_ = tot;
    arr[now].nxt_ = tot;
    idx[y] = tot;
}

//y插到x的左边(前面)
void ins_front(int x, int y)
{
    // int now = find(x);
    int now = idx[x];
    arr[++tot] = Node(arr[now].pre_, now, y);
    arr[arr[now].pre_].nxt_ = tot;
    arr[now].pre_ = tot;
    idx[y] = tot;
}

//找到x的下标，并删除它
void del(int x)
{
    // int now = find(x);
    int now = idx[x];
    if (!now)
        return;
    int pre = arr[now].pre_, nxt = arr[now].nxt_;
    arr[nxt].pre_ = pre;
    arr[pre].nxt_ = nxt;
    idx[x] = 0;
}

//输出链表
void print()
{
    int now = dummyhead.nxt_;
    while (now)
    {
        cout << arr[now].key_ << " ";
        now = arr[now].nxt_;
    }
}

int main()
{
    int n, m, t, k, p;
    //初始状态有个1
    ins_back(0, 1);
    cin >> n;
    for (int i = 2; i <= n; ++i)
    {
        cin >> k >> p;
        if (p == 0)
            ins_front(k, i);
        else
            ins_back(k, i);
    }
    cin >> m;
    while (m--)
    {
        cin >> t;
        del(t);
    }
    print();
    return 0;
}

思路

链表增删查改操作的模板题，直接看题解就行

这里有个注意点，不能每次搜索后再删除，这样时间复杂度高达\(O\left( n^2 \right)\)会超时

需要设置一个下标数组idx，存放每个数字对应的节点编号来替代find函数

其实这里也不需要删除操作，额外新建一个标记数组记录需要被删除的数字，输出时跳过即可