解题思路

栈模拟

按目标从底到顶依次“定格”每个目标元素 x：

• 持续从预备区把积木 next 扔到堆叠区（执行 In），直到把 x 压入栈顶。
• 对于中间被压入的非目标数（next != x），立刻执行一次 Out 丢弃，保证不会破坏已定格的下层结构。
• 当压入的正好是 x 时，不再 Out，保留在栈中，进入下一个目标。

完成全部目标后即可停止（无需处理余下的预备区积木）。

复杂度分析

• 时间复杂度：O(n)（每个积木最多一次 In 与一次 Out 检查/操作）。
• 空间复杂度：O(1)（除输出外只用常数变量；如不显式维护栈，直接构造操作序列即可）。

代码实现

Python

import sys

def solve():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    n, m = data[0], data[1]
    target = data[2:2+m]

    ops = []
    nxt = 1  # 下一个将从预备区取出的编号

    for x in target:
        # 一直取到 x 为止
        while nxt <= x:
            ops.append("In")
            if nxt != x:
                ops.append("Out")  # 中间数不是目标，立即丢弃
            nxt += 1
        # 现在栈顶保留了 x，不执行 Out

    print(",".join(ops))

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> all = new ArrayList<>();
        String line;
        // 读到所有整数
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (line.isEmpty()) continue;
            StringTokenizer st = new StringTokenizer(line);
            while (st.hasMoreTokens()) all.add(Integer.parseInt(st.nextToken()));
        }
        if (all.size() < 2) return;
        int n = all.get(0), m = all.get(1);
        int[] target = new int[m];
        for (int i = 0; i < m; i++) target[i] = all.get(2 + i);

        StringBuilder ans = new StringBuilder();
        int nxt = 1; // 将要 In 的编号
        boolean first = true;

        for (int x : target) {
            while (nxt <= x) {
                if (!first) ans.append(",");
                ans.append("In");
                first = false;
                if (nxt != x) {
                    ans.append(",Out");
                }
                nxt++;
            }
            // 栈顶为 x，保留
        }
        System.out.println(ans.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(m);
    for (int i = 0; i < m; ++i) cin >> a[i];

    vector<string> ops;
    int nxt = 1;
    for (int x : a) {
        while (nxt <= x) {
            ops.push_back("In");
            if (nxt != x) ops.push_back("Out");
            ++nxt;
        }
        // x 留在栈上
    }
    for (int i = 0; i < (int)ops.size(); ++i) {
        if (i) cout << ",";
        cout << ops[i];
    }
    cout << "\n";
    return 0;
}

题目内容

有玩过叠叠高游戏么。

假设，预定给出一组积木，为其编号 $list=[1,2,3,...,n]$ 。

游戏只有两种操作，所有的积木都是按顺序放在预备区。

积木可以放到预备区和堆叠区，在这两个区域里面，要必须先拿最上面的积木才能拿下面的积木。

第一种 $In$ ，表示把积木从预备区拿到堆叠区。

第二种 $Out$ ，表示把积木从堆叠区拿走并丢弃。

给定一个结束状态，求能通过 $In$ 和 $Out$ 的操作序列，得出该结束状态。

输入描述

输入第一行为 $n$ 和 $m$ ，表示积木的总数目和目标积木的数量；

输入第二行为 $m$ 个数，为目标积木排列；

最多有 $100$ 个积木。

输出描述

输出一行为操作序列，用 , 隔开输出保证合法。

样例1

输入

3 2
1 3

输出

In,In,Out,In

说明

读取数字 $1$ ，将 $1$ 移到堆叠区中 $[1]$

读取数字 $2$ ，将 $2$ 移到堆叠区中 $[1,2]$ ，然后将其 $Out$ ，现在堆叠区为 $[1]$

读取数字 $3$ ，将 $3$ 移动堆叠区中 $[1,3]$

样例2

输入

3 3
1 2 3

输出

In,In,In

样例3

输入

4 2
1 2

输出

In,In

说明

放了 $1$ 和 $2$ 之后即可停止。