题解 | #插队#_牛客博客

题目链接

插队

题目描述

模拟一个奶茶店排队的过程。初始有 $N$ 位顾客排成一队。接下来发生 $M$ 次插队事件，每次事件一个名为 u 的顾客会移动到名为 v 的顾客前面。你需要输出所有事件处理完毕后的最终队列。

这是一个主函数模式 (Main Function Mode) 的题目，你需要自己处理输入和输出。

输入格式:

第一行两个整数 $N, M$ 。
第二行 $N$ 个字符串，表示初始队列。
接下来 $M$ 行，每行两个字符串 u v，表示顾客 u 移动到 v 前面。

输出格式:

一行字符串，表示最终的队列顺序，用空格隔开。

示例: 输入:

4 6
alpha bravo charlie delta
bravo alpha
charlie alpha
delta alpha
charlie bravo
delta bravo
charlie delta

输出:

charlie delta bravo alpha

解题思路

这道题的核心是模拟 "移除" 和 "插入" 这两个操作。如果直接使用普通数组（如 vector）来模拟，每次操作都需要移动大量元素，时间复杂度为 $\mathcal{O}(N)$ ，在 $M$ 次操作下总复杂度为 $\mathcal{O}(M \cdot N)$ ，可能会超时。

一个非常高效的思路是，用数组来模拟双向链表。这种方法在竞赛编程中很常见，因为它避免了频繁的动态内存分配，并且能让我们对数据布局有更直接的控制。

算法步骤:

数据结构:
- name_to_id (哈希表/Map): 建立一个从顾客 string 类型名字到其唯一 int 类型 ID 的映射。
- id_to_name (数组/Vector): 建立一个从唯一 ID 到顾客名字的映射，方便最后输出。
- prev 和 next 数组: prev[i] 存储 ID 为 i 的顾客的前一个顾客的 ID；next[i] 存储后一个顾客的 ID。
- 哨兵 (Sentinels): 为了简化对队首和队尾的操作，我们引入两个虚拟的"哨兵"节点：head（ID 为 0）和 tail（ID 为 N+1）。head 永远在队首之前，tail 永远在队尾之后。
初始化:
- 读取 $N$ 和 $M$ 。
- 为 $N$ 个顾客分配 1 到 $N$ 的唯一 ID，并填充 name_to_id 和 id_to_name。
- 初始化 prev 和 next 数组，构建出初始队列。整个队列看作 head -> 1 -> 2 -> ... -> N -> tail。
  - next[0] = 1; prev[0] = -1; (head的前驱无效)
  - prev[N+1] = N; next[N+1] = -1; (tail的后继无效)
  - 对于 i 从 1 到 $N$ ，next[i] = i + 1, prev[i] = i - 1。
处理插队事件 (u 插到 v 前面):
- 对于每次事件，通过 name_to_id 查到 u 和 v 的ID: u_id, v_id。
- 执行移动操作 (本质是修改数组值): a. 从链表中"摘下" u_id: 设 u_id 的前驱是 u_prev_id，后继是 u_next_id。我们让 u_prev_id 的后继直接指向 u_next_id，让 u_next_id 的前驱直接指向 u_prev_id。这对应于修改 next[u_prev_id] 和 prev[u_next_id] 的值。 b. 将 u_id 插入到 v_id 之前: 设 v_id 的前驱是 v_prev_id。现在需要将 u_id 插入到 v_prev_id 和 v_id 之间。这需要修改 u_id, v_id, 和 v_prev_id 三者对应的 prev 和 next 数组项，以建立新的连接关系。
- 由于所有操作都只是数组的赋值，单次事件的复杂度是 $\mathcal{O}(1)$ (如果忽略哈希表查找的时间)。
输出结果:
- 所有事件处理完毕后，从 head (ID 0) 的 next 开始，沿着 next 数组不断跳转，直到遇到 tail (ID N+1)，依次将ID通过 id_to_name 转换成名字并输出。

代码

cpp
java
python

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    map<string, int> name_to_id;
    vector<string> id_to_name(n + 1);
    vector<int> prev_arr(n + 2);
    vector<int> next_arr(n + 2);

    // 初始化，为N个顾客分配ID 1到N
    for (int i = 1; i <= n; ++i) {
        string name;
        cin >> name;
        name_to_id[name] = i;
        id_to_name[i] = name;
    }

    // 构建初始的双向链表连接
    // 0是head哨兵, n+1是tail哨兵
    next_arr[0] = 1;
    prev_arr[n + 1] = n;
    for (int i = 1; i <= n; ++i) {
        prev_arr[i] = i - 1;
        next_arr[i] = i + 1;
    }

    // 处理M次事件
    for (int i = 0; i < m; ++i) {
        string u_name, v_name;
        cin >> u_name >> v_name;

        int u_id = name_to_id[u_name];
        int v_id = name_to_id[v_name];

        // 1. 从链表中"摘下" u
        int u_prev = prev_arr[u_id];
        int u_next = next_arr[u_id];
        next_arr[u_prev] = u_next;
        prev_arr[u_next] = u_prev;

        // 2. 将 u 插入到 v 之前
        int v_prev = prev_arr[v_id];
        next_arr[v_prev] = u_id;
        prev_arr[u_id] = v_prev;
        next_arr[u_id] = v_id;
        prev_arr[v_id] = u_id;
    }

    // 输出最终队列
    bool first = true;
    for (int curr_id = next_arr[0]; curr_id != n + 1; curr_id = next_arr[curr_id]) {
        if (!first) {
            cout << " ";
        }
        cout << id_to_name[curr_id];
        first = false;
    }
    cout << endl;

    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Map<String, Integer> nameToId = new HashMap<>();
        String[] idToName = new String[n + 1];
        int[] prev = new int[n + 2];
        int[] next = new int[n + 2];

        // 初始化，分配ID 1到N
        for (int i = 1; i <= n; i++) {
            String name = sc.next();
            nameToId.put(name, i);
            idToName[i] = name;
        }

        // 构建初始链表连接, 0是head, n+1是tail
        next[0] = 1;
        prev[n + 1] = n;
        for (int i = 1; i <= n; i++) {
            prev[i] = i - 1;
            next[i] = i + 1;
        }

        // 处理M次事件
        for (int i = 0; i < m; i++) {
            String uName = sc.next();
            String vName = sc.next();

            int uId = nameToId.get(uName);
            int vId = nameToId.get(vName);
            
            // 1. 从链表中"摘下"u
            int uPrevId = prev[uId];
            int uNextId = next[uId];
            next[uPrevId] = uNextId;
            prev[uNextId] = uPrevId;

            // 2. 将u插入到v之前
            int vPrevId = prev[vId];
            next[vPrevId] = uId;
            prev[uId] = vPrevId;
            next[uId] = vId;
            prev[vId] = uId;
        }

        // 输出最终队列
        StringBuilder sb = new StringBuilder();
        int currId = next[0];
        while (currId != n + 1) {
            sb.append(idToName[currId]);
            if (next[currId] != n + 1) {
                sb.append(" ");
            }
            currId = next[currId];
        }
        System.out.println(sb.toString());
    }
}

def main():
    n, m = map(int, input().split())
    initial_queue = input().split()

    name_to_id = {}
    id_to_name = [""] * (n + 1) # id从1到n
    
    # 数组模拟双向链表
    # 0是head哨兵, n+1是tail哨兵
    prev_arr = [0] * (n + 2)
    next_arr = [0] * (n + 2)

    # 初始化，分配ID 1到n
    for i, name in enumerate(initial_queue):
        user_id = i + 1
        name_to_id[name] = user_id
        id_to_name[user_id] = name

    # 构建初始连接
    next_arr[0] = 1
    prev_arr[n + 1] = n
    for i in range(1, n + 1):
        prev_arr[i] = i - 1
        next_arr[i] = i + 1

    # 处理M次事件
    for i in range(m):
        u_name, v_name = input().split()
        u_id = name_to_id[u_name]
        v_id = name_to_id[v_name]
        
        # 如果u已经在v前面，无需操作
        if next_arr[u_id] == v_id:
            continue

        # 1. "摘下" u
        u_prev_id = prev_arr[u_id]
        u_next_id = next_arr[u_id]
        next_arr[u_prev_id] = u_next_id
        prev_arr[u_next_id] = u_prev_id

        # 2. 插入 u 到 v 之前
        v_prev_id = prev_arr[v_id]
        next_arr[v_prev_id] = u_id
        prev_arr[u_id] = v_prev_id
        next_arr[u_id] = v_id
        prev_arr[v_id] = u_id

    # 输出结果
    result = []
    curr_id = next_arr[0]
    while curr_id != n + 1:
        result.append(id_to_name[curr_id])
        curr_id = next_arr[curr_id]
    
    print(" ".join(result))

if __name__ == "__main__":
    main()

算法及复杂度

算法: 数组模拟双向链表 + 哈希表/Map
时间复杂度: $\mathcal{O}((N + M) \log N)$ (对于C++的map) 或 $\mathcal{O}(N+M)$ (对于Java/Python的哈希表)。
- 初始化：填充 name_to_id 和 id_to_name 需要 $\mathcal{O}(N)$ (Java/Python) 或 $\mathcal{O}(N \log N)$ (C++)。初始化 prev 和 next 数组需要 $\mathcal{O}(N)$ 。
- 每次事件：查找ID需要 $\mathcal{O}(\log N)$ (C++) 或 $\mathcal{O}(1)$ (Java/Python)。修改数组是 $\mathcal{O}(1)$ 。
- 输出：遍历需要 $\mathcal{O}(N)$ 。
- 总体上，C++版本由 map 的查找决定，Java/Python版本由线性扫描决定。
空间复杂度: $\mathcal{O}(N)$ 。
- 需要 $\mathcal{O}(N)$ 空间存储 name_to_id, id_to_name, prev, next。