题目描述

模拟一个自动包装机的操作。该机器包含：
1. N 条轨道 (Track)：编号从 1 到 N。每条轨道初始时放置 M 个物品（用大写英文字母表示）。物品按从左到右的顺序排列，最左边的物品位于轨道尽头。
2. 一个筐 (Basket)：有最大容量 $S_{max}$。物品放入筐中时，后放入的物品会叠在先放入的物品之上。
3. 一条流水线 (Conveyor Belt)：用于收集从筐中取出的物品。
4. N+1 个按钮:
* 按钮 i (1 ≤ i ≤ N)：按下时，如果轨道 i 非空，活塞会将轨道 i 最左边（尽头）的一个物品推落到筐的顶部。
* 特殊情况：如果按下按钮 i 时筐已满（达到容量 $S_{max}$），系统会先强制执行一次按钮 0 的操作（从筐顶部取出一个物品放到流水线上），然后再将轨道 i 的物品推入筐中。
* 如果轨道 i 为空，按下按钮 i 无任何效果。
* 按钮 0: 按下时，如果筐非空，机械手会从筐顶部抓取一个物品，并将其放到流水线上。
* 如果筐为空，按下按钮 0 无任何效果。

给定 N, M, $S_{max}$，N 条轨道的初始物品序列，以及一系列按下的按钮编号（以 -1 结束）。要求按顺序输出最终出现在流水线上的所有物品。

样例

输入:
3 4 4
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1

输出:
MATA

算法 (模拟 + 数据结构)

$O(\text{总操作次数} + N \times M)$

思路分析

本题的核心是精确地模拟自动包装机的运作过程。我们需要选择合适的数据结构来表示机器的各个部件，并根据按钮操作更新它们的状态。

1. 数据结构选择:

   • 轨道 (Tracks): 每条轨道上的物品有明确的顺序，新物品总是从最左边（尽头）被推出。这符合 队列 (Queue) 的先进先出 (FIFO) 特性，或者更准确地说，是双端队列 (Deque)，因为我们可以方便地从前端移除元素 (pop_front)。我们使用 vector<deque<char>> tracks 来存储 N 条轨道，tracks[i] 代表第 i+1 条轨道 (0-based 索引)。
   • 筐 (Basket): 物品放入筐中是叠加上去的，取出时总是从顶部取出。这完全符合 栈 (Stack) 的后进先出 (LIFO) 特性。我们使用 stack<char> basket 来表示筐。
   • 流水线 (Conveyor Belt): 流水线上的物品是按顺序添加的。使用一个 string ans 来存储流水线上的物品序列，每次有物品放到流水线上时，将其追加到字符串末尾。

2. 初始化:

   • 读取 N, M, $S_{max}$。
   • 创建 tracks 向量，大小为 N。
   • 对于每条轨道 i (0 到 N-1)，读取包含 M 个字符的字符串 initial_items。将 initial_items 中的每个字符依次 push_back 到 tracks[i] 这个 deque 中。这样，字符串的第一个字符（最左边的物品）就位于 deque 的 front。
   • 创建空的 basket 栈。
   • 创建空的 ans 字符串。

3. 模拟操作:

   • 循环读取按钮编号 button，直到读到 -1。
   • 处理按钮 0:
     • 检查筐是否为空 (!basket.empty())。
     • 如果非空，取出筐顶部的物品 (basket.top())，将其追加到 ans 字符串 (ans += ...)，然后将该物品从筐中移除 (basket.pop())。
   • 处理按钮 i (1 ≤ i ≤ N):
     • 将按钮编号转换为 0-based 的轨道索引 track_index = button - 1。
     • 检查轨道索引是否有效 (track_index >= 0 && track_index < n) 并且对应的轨道是否非空 (!tracks[track_index].empty())。
     • 如果轨道有效且非空：
       • 检查筐是否已满: if (basket.size() == s_max)。
       • 如果筐已满，执行强制的按钮 0 操作：取出筐顶物品 (basket.top())，加入 ans，然后 basket.pop()。
       • 从轨道的尽头（deque 的前端）获取物品：char item = tracks[track_index].front()。
       • 将该物品放入筐中（压入栈顶）：basket.push(item)。
       • 将该物品从轨道中移除（从 deque 前端弹出）：tracks[track_index].pop_front()。
   • 如果按钮编号无效，或对应轨道为空，或按钮为 0 且筐为空，则不执行任何操作，直接进入下一次循环。

4. 输出:

   • 循环结束后，ans 字符串中就包含了按顺序放到流水线上的所有物品。输出 ans。

时间复杂度

• 初始化: 读取 N, M, $S_{max}$ 是 O(1)。读取 N 条轨道的 M 个物品并存入 deque 需要 O(N * M) 的时间。初始化栈和字符串是 O(1)。
• 模拟操作: 设按钮操作的总次数为 P。每次操作：
  • 按钮 0: 栈操作 (top, pop) 和字符串追加 (+=) 都是 O(1) 或摊销 O(1)。
  • 按钮 i: 检查轨道非空 (O(1))，检查栈大小 (O(1))，可能的栈操作 (O(1))，deque 前端访问/移除 (front, pop_front) 都是 O(1)，栈压入 (push) 是 O(1)。
  • 因此，处理每次按钮操作的时间复杂度是 O(1)。
• 总时间复杂度: O(N * M + P)，其中 P 是按钮操作的总次数。考虑到数据范围，$N \times M \le 100 \times 1000 = 10^5$，$P \le 10^5$，总复杂度在可接受范围内。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (本题未使用)

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int n;        // 轨道的条数
    int m;        // 每条轨道初始物品数量
    int s_max;    // 筐的最大容量
    cin >> n >> m >> s_max;

    // 使用 vector<deque<char>> 来存储 N 条轨道
    // tracks[i] 代表第 i+1 条轨道 (0-based index)
    vector<deque<char>> tracks(n);
    // 读取每条轨道的初始物品
    for (int i = 0; i < n; i++) {
        string initial_items;
        cin >> initial_items;
        // 将物品放入对应的 deque，保持输入顺序 (最左边的物品在 deque 前端)
        for (char item : initial_items) {
            tracks[i].push_back(item); // push_back 使输入串的第一个字符在 deque::front()
        }
    }

    // 使用 stack<char> 来模拟筐 (后进先出)
    stack<char> basket;

    // 使用 string 来存储流水线上的物品序列
    string ans = "";

    int button; // 用于存储当前按下的按钮编号
    // 循环读取按钮编号，直到遇到 -1
    while (cin >> button && button != -1) {
        // 处理按钮 0 (从筐取物到流水线)
        if (button == 0) {
            // 检查筐是否非空
            if (!basket.empty()) {
                // 取出顶部物品，加入流水线序列
                ans += basket.top();
                // 从筐中移除物品
                basket.pop();
            }
        // 处理按钮 1 到 N (从轨道取物到筐)
        } else {
            // 将按钮编号转换为 0-based 轨道索引
            int track_index = button - 1;
            // 检查轨道索引是否有效，且对应轨道是否非空
            if (track_index >= 0 && track_index < n && !tracks[track_index].empty()) {

                // 检查筐是否已满
                if (basket.size() == s_max) {
                    // 筐满，强制执行按钮 0 操作
                    ans += basket.top();
                    basket.pop();
                }

                // 从轨道前端取出物品，放入筐顶
                basket.push(tracks[track_index].front());
                // 从轨道前端移除该物品
                tracks[track_index].pop_front();
            }
            // 如果轨道索引无效或轨道为空，则不执行任何操作
        }
    }

    // 输出流水线上的物品序列
    cout << ans << "\n";

    return 0; // 程序正常结束
}