题解 CF637B 【Chat Order】

UperFicial · 2020-10-24 09:55:14 · 题解

不同于其它题解的做法

前言

逗比题，但显然我 WA 了一次/kk

网址：\text{Link}

这里讲一个不同于其它题解的做法。

题意

有 n 个单词，你需要顺序将它们插入到队首，若这个单词已经在队列中，那么就把原来的那个单词移至队首，问你最后这个队列长啥样。

题解

这完全就是个模拟题，但如果要暴力模拟显然 T 飞。

不过我们发现，题目中涉及了很多的删除和插入操作，链表这一简单的数据结构便可 O(1) 解决。

我们定义一个双向链表 lst，其中额外有一个 string 类型的变量的 x，代表这个位置存的 string。

但是链表如果在队首放元素貌似不太好办，我们可以先把每个单词放到队尾，到时候反着输出就 OK 了。

在队尾插入一个元素是很好解决的，只要把尾指针 +1 后赋值就好了：

void push_end(string x)
{
    tail++;
    lst[tail].x=x;
    return;
}

将全部数据插入后，再用一次 O(n) 的时间去重，我们定义 pos[s] 为字符串 s 在 lst 中的位置。为什么要设立这个 pos，是因为我们对于每个 s' 可以知道它有没有出现过，没有出现过显然它就不动，并将 pos[s'] 赋值，否则就说明已经出现过，我们需将上一个位置直接删除，但别忘了再更新 pos[s'] 的位置，因为上一个元素已经删除了，真正的位置已经变了。

时空复杂度：O(n)。

code