题目描述

模拟一个制作人造松枝的过程。工人使用一个推送器提供的松针序列、一个有限容量的小盒子（作为临时存储，后进先出）和一个空的松枝干来组装松枝。

核心规则:
1. 组件:
* 推送器：按顺序提供 $N$ 片松针，大小为正整数。
* 小盒子：容量为 $M$，行为像一个栈（后进先出 LIFO）。
* 松枝干：容量为 $K$，即最多插 $K$ 片松针。
2. 组装过程 (针对一根松枝):
* 第一片松针: 先尝试从小盒子顶部取。如果盒子为空，则从推送器取一片。将这片松针插在枝干最底部。
* 后续松针: 目标是再插一片松针。
* 约束: 新插的松针大小必须 小于或等于 前一片插上的松针大小。
* 来源优先级:
1. 检查小盒子顶部：如果非空且满足约束，则取出并插入。
2. 如果小盒子不满足（空或顶部松针太大）：检查推送器。
* 循环从推送器取松针 next_needle：
* 如果 next_needle 满足约束，则插入，停止为当前位置寻找松针。
* 如果 next_needle 不满足约束：
* 如果小盒子未满 (size < M)，将 next_needle 放入小盒子。继续从推送器取下一片。
* 如果小盒子已满 (size == M)，则不能放入盒子，也不能使用这片松针。将这片松针退回推送器（逻辑上，即不消耗它），停止为当前位置寻找松针（意味着当前松枝可能无法继续添加）。
* 如果推送器取完了仍然没有找到合适的松针，停止为当前位置寻找松针。
* 如果成功插入了一片松针，则重复此过程（直到松枝满或无法插入）。
3. 结束一根松枝的制作: 当以下任一情况发生时，当前松枝完成制作，并开始下一根：
* (1) 盒子满且推送器不满足: 在尝试从推送器取松针 next_needle 时，发现 next_needle 不满足尺寸约束，并且此时小盒子已满。将当前松枝视为成品，并将 next_needle 退回推送器。
* (2) 盒子不满足且推送器空: 尝试从盒子取松针，发现不满足约束（或盒子空），然后尝试从推送器取，发现推送器已经没有松针了。将当前松枝视为成品。
* (3) 松枝满: 松枝上已插入 $K$ 片松针。将当前松枝视为成品。
4. 整体结束: 当推送器耗尽 并且 小盒子为空时，整个流程结束。
5. 输出: 按制作完成的顺序，输出每根成品松枝上的松针大小（从底部到顶部，即按插入顺序）。

样例

输入:
8 3 4
20 25 15 18 20 18 8 5

输出:
20 15
20 18 18 8
25 5

算法 (模拟 + 栈)

$O(N)$

思路分析

这个问题本质上是一个过程模拟题。我们需要精确地按照题目描述的规则来操作推送器、小盒子和当前松枝。

1. 数据结构选择:

   • 推送器 (Feeder): 可以用一个 std::vector<int> 存储输入的松针序列，并用一个整数 idx 作为指针，指示下一个要从推送器取的松针的索引。
   • 小盒子 (Box): 题中明确指出“工人每次只能取出最上面（即最后放入）的一片”，这是典型的栈（Stack）行为。我们可以使用 std::stack<int> 来模拟。需要注意栈的容量限制 $M$。
   • 当前松枝 (Branch): 需要按顺序记录插入的松针。使用 std::vector<int> 是合适的，方便按顺序添加 (push_back) 和访问最后一个元素 (back()) 来检查尺寸约束。同时也方便最后按顺序输出。

2. 主循环:
   整个过程是制作一根又一根松枝，直到无法再制作（推送器和小盒子都空了）。这可以用一个 while 循环来控制。循环条件是 idx < n || !box.empty()，表示只要推送器里还有松针或者盒子里还有松针，就可能需要继续制作。

3. 制作单根松枝:
   在 while 循环内部，我们开始制作一根新的松枝。

   • 初始化 std::vector<int> branch;
   • 获取第一片松针:
     • 检查 box 是否为空。如果不空，从 box 弹出一个元素放入 branch。
     • 如果 box 为空，检查 idx < n。如果是，从 feeder[idx] 取一个元素放入 branch，并 idx++。
     • 如果 box 和 feeder 都为空，那么无法开始新松枝，应该跳出主循环（或者主循环条件会自然终止）。
   • 获取后续松针 (循环直到松枝满或无法添加): 使用一个内层 while (branch.size() < k) 循环。
     • 设置一个标志 bool added = false; 用于标记本轮是否成功添加了松针。
     • 尝试从盒子获取:
       • if (!box.empty() && box.top() <= branch.back()): 如果盒子非空且顶部松针满足尺寸约束。
       • branch.push_back(box.top()); box.pop(); added = true;
     • 如果盒子不满足，尝试从推送器获取:
       • else { ... }: 进入这个 else 块意味着盒子要么是空的，要么顶部的松针太大。
       • while (idx < n): 循环地从推送器取。
         • int next = feeder[idx++];: 取出推送器上的下一个松针，并预先移动指针。
         • if (next <= branch.back()): 如果满足尺寸约束。
           • branch.push_back(next); added = true; break;: 添加到松枝，设置标志，跳出 推送器循环。
         • else if (box.size() < m): 如果不满足约束，但盒子有空间。
           • box.push(next);: 将不合适的松针放入盒子。继续 推送器循环 尝试下一个。
         • else: 如果不满足约束，且盒子已满 (size == m)。这是终止条件 (1) 的触发点。
           • idx--;: 将推送器指针退回，表示这个 next 松针没有被消耗，也没有放入盒子。
           • break;: 跳出 推送器循环。此时 added 仍然是 false。
       • if (idx >= n && !added) break;: 如果推送器已经取完 (idx >= n) 并且仍然没有成功添加松针 (!added)，这意味着触发了终止条件 (2) (盒子不满足且推送器空)。跳出 获取后续松针的主循环。
     • if (!added) break;: 如果在尝试了盒子和推送器之后，added 仍然是 false（这发生在触发了终止条件 1 或 2 时），则跳出 获取后续松针的主循环。
   • 输出成品松枝: 内层 while 循环结束后（因为松枝满 K，或者触发了条件 1 或 2），打印 branch 中的所有元素。

4. 代码细节:

   • 使用 C++ 的 stack 和 vector。
   • 注意 idx 的管理，特别是当盒子满且推送器松针不合适时，需要 idx--。
   • 输出格式要求空格分隔，行尾无多余空格。一个简单的处理方法是循环打印前 size-1 个元素加空格，最后单独打印最后一个元素。或者像示例代码那样，在循环中判断是否是最后一个元素来决定是否打印空格。

时间复杂度

• 每个松针最多被从推送器取出一次 (idx 从 0 增加到 n)。
• 每个松针最多被放入盒子一次，然后从盒子取出一次。
• 每个松针最多被放入当前松枝一次。
• 所有操作（push, pop, top, back, push_back, 索引访问, 比较, 算术运算）都是 O(1) 的。
• 因此，整个模拟过程的时间复杂度是线性的，即 $O(N)$。

空间复杂度

• feeder vector: $O(N)$。
• box stack: 最多存储 $M$ 个元素， $O(M)$。
• branch vector: 最多存储 $K$ 个元素， $O(K)$。
• 总空间复杂度为 $O(N + M + K)$。根据数据范围，主要是 $O(N)$。

C++ 代码

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

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (虽然本题没用到)

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k; // N: 推送器数量, M: 盒子容量, K: 松枝容量
    cin >> n >> m >> k;
    vector<int> feeder(n); // 存储推送器上的松针大小
    for (int i = 0; i < n; i++) {
        cin >> feeder[i];
    }

    stack<int> box; // 小盒子，使用栈模拟 LIFO
    int idx = 0; // 推送器的当前索引

    // 主循环：只要推送器或盒子还有松针，就继续尝试制作
    while (idx < n || !box.empty()) {
        vector<int> branch; // 当前正在制作的松枝

        // 步骤1：获取第一片松针
        if (!box.empty()) { // 优先从盒子取
            branch.push_back(box.top());
            box.pop();
        } else if (idx < n) { // 盒子空，从推送器取
            branch.push_back(feeder[idx++]);
        } else { // 盒子和推送器都空了，无法开始新松枝，结束
            break; 
        }

        // 步骤2：获取后续松针，直到松枝满 (size == k) 或无法添加
        while (branch.size() < k) {
            bool added = false; // 标记本轮是否成功添加了松针

            // 尝试从盒子获取
            if (!box.empty() && box.top() <= branch.back()) {
                branch.push_back(box.top());
                box.pop();
                added = true;
            } else { 
                // 盒子不满足 (空或顶部太大)，尝试从推送器获取
                while (idx < n) { // 只要推送器还有
                    int next = feeder[idx++]; // 取出下一个，预先移动指针
                    if (next <= branch.back()) { // 满足约束
                        branch.push_back(next);
                        added = true;
                        break; // 成功添加，跳出推送器循环
                    } else if (box.size() < m) { // 不满足约束，但盒子有空间
                        box.push(next); // 放入盒子
                        // 继续推送器循环，尝试下一个
                    } else { // 不满足约束，且盒子已满 (终止条件 1 触发点)
                        idx--; // 将指针退回，此松针未被消耗
                        break; // 跳出推送器循环，added 仍为 false
                    }
                }
                // 检查是否因推送器耗尽而退出推送器循环，且未添加成功 (终止条件 2 触发点)
                if (idx >= n && !added) {
                    break; // 跳出获取后续松针的主循环
                }
            }

            // 如果本轮尝试了盒子和推送器后，仍未添加成功 (触发了条件 1 或 2)
            if (!added) {
                break; // 跳出获取后续松针的主循环
            }
            // 否则 (added 为 true)，继续内层 while 循环，尝试添加下一片
        }

        // 步骤3：输出完成的松枝
        for (int i = 0; i < branch.size(); i++) {
            cout << branch[i];
            if (i < branch.size() - 1) { // 控制空格，行尾无空格
                cout << " ";
            }
        }
        cout << "\n"; // 每根松枝占一行
    }

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