双栈排序

形式化题目

给定一个 $1 \sim n$ 的排列 $P$ ，允许使用两个栈 $S_1, S_2$ 进行四种操作：

a: 将输入序列的第一个元素压入 $S_1$
b: 将 $S_1$ 栈顶元素弹出至输出序列
c: 将输入序列的第一个元素压入 $S_2$
d: 将 $S_2$ 栈顶元素弹出至输出序列

要求判断是否可以通过一系列操作将排列升序排序（即最终输出为 $1, 2, \dots, n$ ）。若不能，输出 0；若能，输出字典序最小的操作序列（由 a, b, c, d 组成，以空格分隔）。

数据范围： $1 \le n \le 1000$ 。

正解

思路

本题的核心在于判断哪些元素绝对不能进入同一个栈。假设元素 $P_i$ 和 $P_j$ （ $i < j$ ）被分到了同一个栈。因为 $i < j$ ， $P_i$ 会先入栈。如果 $P_i < P_j$ ，为了按升序输出， $P_i$ 必须在 $P_j$ 之前出栈。如果此时输入序列中还有某个元素 $P_k$ （ $k > j$ ）满足 $P_k < P_i$ ，那么 $P_i$ 就不能在 $P_j$ 入栈前出栈（因为比 $P_i$ 更小的 $P_k$ 还没进入体系被处理）。这样一来， $P_j$ 必然会被压在 $P_i$ 之上，导致较大的数压在较小的数上面，这在要求升序输出的栈排序中是非法的。

因此，两个元素 $P_i$ 和 $P_j$ 不能在同一个栈的充要条件是：

i < j \quad \text{且} \quad P_i < P_j \quad \text{且} \quad \exists k > j, \ P_k < P_i

我们可以预处理一个后缀最小值数组 min_val，其中 min_val[i] 表示 $P_i \sim P_n$ 中的最小值。上述冲突条件即可化简为： $i < j \land P_i < P_j \land \text{min\_val}[j+1] < P_i$ 。

对于所有满足冲突条件的点对 $(i, j)$ ，我们在它们之间连一条无向边，表示它们必须进入不同的栈。

如果该冲突图不是二分图（无法用两种颜色染色），说明无论怎么分配都会产生冲突，即无法排序，输出 0。
如果是二分图，则一定可以排序。由于题目要求字典序最小，且字典序 a < b < c < d，我们应该尽可能让元素提前进入 $S_1$ 。因此，在给二分图的每个连通块染色时，我们将第一个未访问的节点固定染成颜色 $1$ （代表分配给 $S_1$ ），然后再 DFS/BFS 染完整个连通块。

染色完成后，每个元素应该进入哪个栈就已经确定了。最后，我们只需按照 a, b, c, d 的优先级顺序，贪心地模拟每一步操作即可：

a 操作：如果当前输入元素属于 $S_1$ ，且 $S_1$ 为空或栈顶元素大于当前元素，则执行 a。
b 操作：如果 $S_1$ 栈顶恰好等于当前需要输出的元素（expected），则执行 b。
c 操作：如果当前输入元素属于 $S_2$ ，且 $S_2$ 为空或栈顶元素大于当前元素，则执行 c。
d 操作：如果 $S_2$ 栈顶恰好等于当前需要输出的元素（expected），则执行 d。

只要能够合法执行，就从上述 1 到 4 尝试，保证字典序是最优的。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 10:05
# update_at: 2026-10-08 10:25

import sys
from collections import deque

type Graph = list[list[int]]  # 邻接表，下标 1..n


def solve_one(n: int, p: list[int]) -> str:
    """求一个排列的双栈排序字典序最小操作序列；不可排序返回 "0"。

    p 用 1 起始下标（p[0] 为占位），返回值形如 "a b a c"。
    """
    # 后缀最小值
    min_val = [10**18] * (n + 2)
    for i in range(n, 0, -1):
        min_val[i] = min(min_val[i + 1], p[i])

    # 冲突图：i < j、P_i < P_j、且 j 之后还有比 P_i 小的 ⟹ 两者不能同栈
    adj: Graph = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        pi = p[i]
        for j in range(i + 1, n + 1):
            if pi < p[j] and min_val[j + 1] < pi:
                adj[i].append(j)
                adj[j].append(i)

    # 二分染色：每个连通块里下标最小的点染 1（S1），让 'a' 尽量靠前
    color = [0] * (n + 1)
    for s in range(1, n + 1):
        if color[s]:
            continue
        color[s] = 1
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v]:
                    if color[v] == color[u]:
                        return "0"
                else:
                    color[v] = 3 - color[u]
                    queue.append(v)

    # 贪心模拟：按 a < b < c < d 尝试；压栈要保持栈内自底向上递减
    s1: list[int] = []
    s2: list[int] = []
    ptr = 1
    want = 1
    ops: list[str] = []
    while want <= n:
        next_value = p[ptr] if ptr <= n else None
        if next_value is not None and color[ptr] == 1 and (not s1 or s1[-1] > next_value):
            s1.append(next_value)
            ops.append("a")
            ptr += 1
        elif s1 and s1[-1] == want:
            s1.pop()
            ops.append("b")
            want += 1
        elif next_value is not None and color[ptr] == 2 and (not s2 or s2[-1] > next_value):
            s2.append(next_value)
            ops.append("c")
            ptr += 1
        elif s2 and s2[-1] == want:
            s2.pop()
            ops.append("d")
            want += 1
        else:
            return "0"  # 理论上不可达
    return " ".join(ops)


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    t = int(next(it))
    out: list[str] = []
    for _ in range(t):
        n = int(next(it))
        p = [0] + [int(next(it)) for _ in range(n)]
        out.append(solve_one(n, p))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 10:05
 * update_at: 2026-10-08 10:25
 */
#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

// 3058《双栈排序》：冲突图 + 二分染色 + 贪心模拟（a < b < c < d）。
//
// ⚠ 输入是多组数据：第一行 T，随后 T 组，每组一行 n、一行 n 个数的排列。
//   题库题面的「输入格式」一节只写了「第一行是一个整数 n」，漏了 T —— 以数据为准。

static string solve_one(int n, const vector<int>& p) {
    // 后缀最小值
    vector<int> min_val(n + 2, 1e9);
    for (int i = n; i >= 1; i--) min_val[i] = min(min_val[i + 1], p[i]);

    // 冲突图：i < j、P_i < P_j、且 j 之后还有比 P_i 小的
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (p[i] < p[j] && min_val[j + 1] < p[i]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    // 二分图染色：每个连通块里下标最小的点染 1（S1），使 'a' 尽量靠前
    vector<int> color(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (color[i]) continue;
        color[i] = 1;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (color[v]) {
                    if (color[v] == color[u]) return "0";   // 非二分图
                } else {
                    color[v] = 3 - color[u];
                    q.push(v);
                }
            }
        }
    }

    // 贪心模拟：按 a < b < c < d 尝试；压栈需保持栈内自底向上递减
    stack<int> s1, s2;
    int expected = 1, ptr = 1;
    vector<char> ops;
    while (expected <= n) {
        if (ptr <= n && color[ptr] == 1 && (s1.empty() || s1.top() > p[ptr])) {
            s1.push(p[ptr]); ops.push_back('a'); ptr++;
        } else if (!s1.empty() && s1.top() == expected) {
            s1.pop(); ops.push_back('b'); expected++;
        } else if (ptr <= n && color[ptr] == 2 && (s2.empty() || s2.top() > p[ptr])) {
            s2.push(p[ptr]); ops.push_back('c'); ptr++;
        } else if (!s2.empty() && s2.top() == expected) {
            s2.pop(); ops.push_back('d'); expected++;
        } else {
            return "0";   // 理论上不可达
        }
    }

    string out;
    for (size_t i = 0; i < ops.size(); i++) {
        if (i) out += ' ';
        out += ops[i];
    }
    return out;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    if (!(cin >> T)) return 0;
    for (int tc = 0; tc < T; tc++) {
        int n;
        if (!(cin >> n)) break;
        vector<int> p(n + 1);
        for (int i = 1; i <= n; i++) cin >> p[i];
        cout << solve_one(n, p) << "\n";
    }
    return 0;
}

复杂度

时间复杂度：预处理后缀最小值需要 $O(n)$ 。建图过程需要双重循环遍历 $i$ 和 $j$ ，时间复杂度为 $O(n^2)$ 。二分图 BFS/DFS 染色遍历所有点和边，时间复杂度为 $O(n^2)$ 。模拟过程最多发生 $2n$ 次进栈和出栈操作，时间复杂度为 $O(n)$ 。因此总时间复杂度为 $O(n^2)$ ，在 $n \le 1000$ 时极为高效。
空间复杂度：需要存储邻接表表示的图，最多有 $O(n^2)$ 条边。空间复杂度为 $O(n^2)$ ，常数较小，完全符合 128 MB 的限制。

总结

核心转化：将“能否放入同一个栈”的问题转化为判定是否存在 $P_k < P_i < P_j\ (i < j < k)$ 的冲突组合，进而转换为无向图的二分染色判定问题。
贪心模拟：由于严谨的冲突排除，安全的进出栈操作一定不会死锁，因此可以严格按照优先级 a > b > c > d 取得字典序最优解，无需回溯。
防坑点：判断连边时的条件必须同时满足三个子条件，遗漏任何一个都会错判；在贪心模拟中，a / c 操作的条件除了检查对应栈的颜色分配，还需判定 top() > P[ptr] 以维持栈内的单调递减性。

目录

形式化题目

正解

思路

代码

复杂度

总结