出题人题解 | #插队#

本题考查链表和关联容器的应用。

插队，就是从队列中删除一个人，再在队列适当位置插入这个人。要在序列中间快速插入、删除元素，最好的选择是使用链表。但在链表中查找元素又是一个难题。为此，我们需要使用关联容器，如红黑树或哈希表，存储元素名称到链表结点地址的对应关系（这里“元素名称”对应顾客名字），即可快速查找元素。

在 C++ 中，链表可以用 std::list 实现，其结点地址可以用迭代器表示，类型是 std::list::iterator；关联容器可以用 std::map（红黑树）或 std::unordered_map（哈希表）实现。在 C++ 中，可以在迭代器所指元素附近插入、删除元素，十分方便。

在 Java 中，链表需手动实现（不建议使用 java.util.LinkedList，其不支持在迭代器所指元素附近插入、删除元素，且其查找元素的内置方法是按下标查找的，时间复杂度较大）；关联容器可以用 java.util.TreeMap（红黑树）或 java.util.HashMap（哈希表）实现。

在 Python 中，链表需手动实现（标准库没有链表）；关联容器可以用字典（dict，哈希表）实现。

在 C 中，……C 中没有关联容器，手动实现也非常复杂，不建议使用。

时间复杂度：（红黑树）；（哈希表）。

空间复杂度：。

C++ 代码：（使用链表迭代器）

#include <iostream>
#include <list>
#include <map>
#include <string>

using namespace std;

int main()
{
    int n = 0, m = 0;
    bool is_not_first = false;
    cin >> n >> m;
    list<string> line;
    map<string, list<string>::iterator> positions;
    for (int i = n; i > 0; --i)
    {
        string s;
        cin >> s;
        line.push_back(s);
        positions[s] = line.end();
        --positions[s];
    }
    for (int i = m; i > 0; --i)
    {
        string x, y;
        cin >> x >> y;
        line.erase(positions[x]);
        positions[x] = line.insert(positions[y], x);
    }
    for (const string& name : line)
    {
        if (is_not_first)
            cout << ' ';
        else
            is_not_first = true;
        cout << name;
    }
    cout << '\n';
}

C++ 代码：（手动实现链表）

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n = 0, m = 0, current = 0;
    bool is_not_first = false;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];
    map<string, int> table;
    table[""] = n;
    for (int i = 0; i < n; ++i)
        table[s[i]] = i;
    vector<int> prevs(n + 1);
    vector<int> nexts(n + 1);
    for (int i = 0; i < n; ++i)
    {
        if (i >= 1)
            prevs[i] = i - 1;
        else
            prevs[i] = n;
        nexts[i] = i + 1;
    }
    nexts[n] = 0;
    prevs[n] = n - 1;
    for (int i = m; i > 0; --i)
    {
        int xi = 0, yi = 0;
        string x, y;
        cin >> x >> y;
        xi = table[x];
        yi = table[y];
        prevs[nexts[xi]] = prevs[xi];
        nexts[prevs[xi]] = nexts[xi];
        nexts[prevs[yi]] = xi;
        nexts[xi] = yi;
        prevs[xi] = prevs[yi];
        prevs[yi] = xi;
    }
    current = nexts[n];
    while (current != n)
    {
        if (is_not_first)
            cout << ' ';
        else
            is_not_first = true;
        cout << s[current];
        current = nexts[current];
    }
    cout << '\n';
}

Java 代码：

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String[] s = new String[n];
        for (int i = 0; i < n; ++i)
            s[i] = sc.next();
        TreeMap<String, Integer> table = new TreeMap<>();
        table.put("", n);
        for (int i = 0; i < n; ++i)
            table.put(s[i], i);
        int[] prevs = new int[n + 1];
        int[] nexts = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            if (i >= 1)
                prevs[i] = i - 1;
            else
                prevs[i] = n;
            nexts[i] = i + 1;
        }
        nexts[n] = 0;
        prevs[n] = n - 1;
        for (int i = m; i > 0; --i) {
            String x = sc.next();
            String y = sc.next();
            int xi = table.get(x);
            int yi = table.get(y);
            prevs[nexts[xi]] = prevs[xi];
            nexts[prevs[xi]] = nexts[xi];
            nexts[prevs[yi]] = xi;
            nexts[xi] = yi;
            prevs[xi] = prevs[yi];
            prevs[yi] = xi;
        }
        int current = nexts[n];
        boolean isNotFirst = false;
        while (current != n) {
            if (isNotFirst)
                System.out.print(' ');
            else
                isNotFirst = true;
            System.out.print(s[current]);
            current = nexts[current];
        }
        System.out.println();
    }
}

Python 代码：

n, m = map(int, input().split())
s = input().split()
table = {}
table[''] = n
for i in range(n):
    table[s[i]] = i
prevs = [0 for _ in range(n + 1)]
nexts = [0 for _ in range(n + 1)]
for i in range(n):
    if i >= 1:
        prevs[i] = i - 1
    else:
        prevs[i] = n
    nexts[i] = i + 1
nexts[n] = 0
prevs[n] = n - 1
for _ in range(m):
    x, y = input().split()
    xi = table[x]
    yi = table[y]
    prevs[nexts[xi]] = prevs[xi]
    nexts[prevs[xi]] = nexts[xi]
    nexts[prevs[yi]] = xi
    nexts[xi] = yi
    prevs[xi] = prevs[yi]
    prevs[yi] = xi
current = nexts[n]
is_not_first = False
while current != n:
    if is_not_first:
        print(' ', end='')
    else:
        is_not_first = True
    print(s[current], end='')
    current = nexts[current]
print()