[NOIP2008-提高] 双栈排序

形式化题目

给定 $1 \sim n$ 的排列 $P$ 与两个栈 $S_1, S_2$ ，只允许四种操作：

a：把输入序列的队头压入 $S_1$ ；
b：把 $S_1$ 栈顶弹出到输出序列末尾；
c：把输入序列的队头压入 $S_2$ ；
d：把 $S_2$ 栈顶弹出到输出序列末尾。

判断是否存在一串操作使输出恰好为 $1, 2, \dots, n$ 。若存在，输出字典序最小的操作序列（按 a < b < c < d 比较，操作之间用空格分隔）；否则输出 $0$ 。

以样例 1（ $P = 1\ 3\ 2\ 4$ ）为例，下表逐操作展示状态变化，它对应答案 a b a a b b a b：

步骤	操作	说明	$S_1$ （右为栈顶）	$S_2$	已输出
1	`a`	压入 1	$[1]$	$[\,]$	$()$
2	`b`	栈顶 1 正是 need，弹出	$[\,]$	$[\,]$	$(1)$
3	`a`	压入 3	$[3]$	$[\,]$	$(1)$
4	`a`	压入 2（比栈顶 3 小，合法）	$[3, 2]$	$[\,]$	$(1)$
5	`b`	弹出 2	$[3]$	$[\,]$	$(1, 2)$
6	`b`	弹出 3	$[\,]$	$[\,]$	$(1, 2, 3)$
7	`a`	压入 4	$[4]$	$[\,]$	$(1, 2, 3)$
8	`b`	弹出 4，输入同时耗尽	$[\,]$	$[\,]$	$(1, 2, 3, 4)$

need 表示下一个必须输出的值。可以看到：每个栈自始至终保持从栈底到栈顶递减，need 一旦进入某个栈就停在栈顶，随叫随到——这个不变量正是后面贪心规则的来源。

正解

思路

朴素想法与瓶颈。 最直接的思路是搜索：每一步四种选择，或者枚举每个元素进哪个栈（ $2^n$ 种分配）再模拟验证。 $n \leqslant 1000$ 时都不可行。它暴露的瓶颈是：我们提前不知道哪些值绝不能进同一个栈，只能盲目枚举。若能先把「必须分家」的值对全部找出来，分栈就从 $2^n$ 种选择退化成一个二分图染色判定。

推导冲突条件。 考察两个位置 $i < j$ 上的值 $x = a[i]$ 、 $y = a[j]$ ，假设它们进了同一个栈：

若 $x$ 在位置 $j$ 之前已经弹出，两者互不干扰，没有冲突。
否则 $y$ 压在 $x$ 上面， $y$ 必然先弹。此时若 $x < y$ ，升序输出却要求 $x$ 先出，矛盾； $x > y$ 则顺序恰好正确，没有冲突。

所以危险情形是 $x < y$ 且 $x$ 拖到 $j$ 之后才弹出。 $x$ 何时才能弹出？必须等所有比 $x$ 小的数都输出完，need 才轮到 $x$ 。于是只要 $j$ 之后还存在比 $x$ 小的数 $a[k]$ （ $k > j$ ），它压入得比 $x$ 晚，会迫使 $x$ 在它之后才弹出——此时 $y$ 早已压在 $x$ 上，矛盾必然发生。得到经典冲突条件：

\exists\, i < j < k \quad \text{使得} \quad a[k] < a[i] < a[j] \;\Longrightarrow\; a[i] \text{ 与 } a[j] \text{ 不能同栈}.

两个方向都不可省：样例 1 中 $a[1] = 1 < a[2] = 3$ ，但位置 2 之后没有比 1 小的数， $1$ 不会被拖住，所以 $1, 3$ 同栈没有问题；反过来 $2\ 3\ 4\ 1$ 中 $2 < 3$ 且后面有 $1 < 2$ ， $2, 3$ 必须分家——事实上该图最终是三角形，怎么分都不够。

建图与染色。 把每个值作为顶点，冲突对连边。一个栈装的值必须两两无冲突，即每个栈是独立集，所以：

图是二分图 ⟺ 两个栈够用，染色方案直接给出每个值进哪个栈；
图含奇环 ⟺ 无论怎么分都不行，输出 $0$ 。

下图是样例 2（ $2\ 3\ 4\ 1$ ）的冲突图， $2, 3, 4$ 两两冲突构成三角形，因此输出 $0$ ：

graph LR
    n2["值 2"] --- n3["值 3"]
    n3 --- n4["值 4"]
    n4 --- n2

染色定完可行性，还差字典序。 二分图每个连通块的染色整体翻转后仍是合法染色，方案不唯一。由于 a 比 c 小，把「在输入中出现最早」的值染成 0（进 $S_1$ ），第一次压入就能拿到更小的 a，同块其余值跟着整体翻转。这是拿到字典序最小答案的第一步。

贪心模拟。 分栈固定后，每步只需在当前合法的操作里取字典序最小者。两条关键规则：

压入必须比栈顶小。若把大值盖在小值上面，小值是将来的 need，被压住后大值只有等 need 先弹，而 need 又被它挡着——死锁，所以 v > 栈顶 的压法一律非法。这条规则保证栈始终递减、need 一旦进栈就停在栈顶，染色合法时模拟绝不会中途卡死。
按 a < b < c < d 取最小合法操作。合法时先压 a，它比 b、d 都小，而且「先压 a 再弹 d」与「先弹 d 再压 a」到达完全相同的状态，晚一步弹不会变差；a 非法时（会盖死栈顶的 need，或比栈顶大）能弹 need 就弹 b——b 比 c、d 都小，且「先弹 b 再压 c」同样与「先压 c 再弹 b」等价；再轮到合法的 c，最后才是 d。输入耗尽后只剩弹出，弹不出 need 即输出 $0$ 。

样例 3（ $2\ 3\ 1$ ）演示全程： $2$ 与 $3$ 冲突（后面有 $1 < 2$ ），染色必须分家，于是得到 a c a b b d：压 2 进 $S_1$ 、压 3 进 $S_2$ 、压 1 进 $S_1$ ，随后依次弹出 $1, 2, 3$ 。

代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 1000000000;

int n;
int a[1005];

// 冲突图 CSR
int deg[1005];
int start_[1006];
vector<int> edges;

// 二分染色，返回 color[1..n]；染不上返回空
vector<int> two_color(int first[]) {
    vector<int> color(n + 1, -1);
    for (int seed = 1; seed <= n; seed++) {
        if (color[seed] != -1) continue;
        color[seed] = 0;
        vector<int> q;
        q.push_back(seed);
        for (size_t qi = 0; qi < q.size(); qi++) {
            int u = q[qi];
            for (int t = start_[u]; t < start_[u + 1]; t++) {
                int v = edges[t];
                if (color[v] == -1) {
                    color[v] = color[u] ^ 1;
                    q.push_back(v);
                } else if (color[v] == color[u]) {
                    return vector<int>();
                }
            }
        }
        // anchor：输入位置最早的成员，翻成 0
        int anchor = q[0];
        for (size_t i = 1; i < q.size(); i++)
            if (first[q[i]] < first[anchor]) anchor = q[i];
        if (color[anchor]) {
            for (size_t i = 0; i < q.size(); i++)
                color[q[i]] ^= 1;
        }
    }
    return color;
}

// 贪心产出字典序最小操作序列；凑不出 1..n 则返回空
string smallest_ops(const vector<int>& color) {
    vector<int> s1, s2;
    vector<string> ops;
    int ptr = 0, need = 1;
    while (need <= n) {
        bool b_now = !s1.empty() && s1.back() == need;
        bool d_now = !s2.empty() && s2.back() == need;
        if (ptr == n) {
            if (b_now) { s1.pop_back(); ops.push_back("b"); }
            else if (d_now) { s2.pop_back(); ops.push_back("d"); }
            else return string();
            need++;
            continue;
        }
        int v = a[ptr];
        bool push_s1 = color[v] == 0 && (s1.empty() || v < s1.back());
        bool push_s2 = color[v] == 1 && (s2.empty() || v < s2.back());
        if (push_s1) { s1.push_back(v); ops.push_back("a"); ptr++; }
        else if (b_now) { s1.pop_back(); ops.push_back("b"); need++; }
        else if (push_s2) { s2.push_back(v); ops.push_back("c"); ptr++; }
        else if (d_now) { s2.pop_back(); ops.push_back("d"); need++; }
        else return string();
    }
    string out;
    for (size_t i = 0; i < ops.size(); i++) {
        if (i) out += " ";
        out += ops[i];
    }
    return out;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) { cout << "0\n"; return 0; }
    for (int i = 0; i < n; i++) cin >> a[i];
    // first[v] = 值 v 在输入里的位置
    int first[1005];
    for (int i = 0; i < n; i++) first[a[i]] = i;

    // build_conflicts
    int suf[1006];
    suf[n + 1] = INF;
    for (int i = n; i >= 1; i--) suf[i] = min(a[i - 1], suf[i + 1]);

    for (int v = 0; v <= n; v++) deg[v] = 0;
    for (int j = 1; j <= n; j++) {
        int mn = suf[j + 1];
        for (int i = 1; i < j; i++) {
            int x = a[i - 1];
            if (mn < x && x < a[j - 1]) {
                deg[x]++;
                deg[a[j - 1]]++;
            }
        }
    }
    start_[1] = 0;
    for (int u = 1; u <= n; u++) start_[u + 1] = start_[u] + deg[u];
    edges.assign(start_[n + 1], 0);
    vector<int> fill(start_, start_ + n + 2);
    for (int j = 1; j <= n; j++) {
        int mn = suf[j + 1];
        for (int i = 1; i < j; i++) {
            int x = a[i - 1];
            if (mn < x && x < a[j - 1]) {
                edges[fill[x]] = a[j - 1];
                fill[x]++;
                edges[fill[a[j - 1]]] = x;
                fill[a[j - 1]]++;
            }
        }
    }

    vector<int> color = two_color(first);
    string ans = color.empty() ? string() : smallest_ops(color);
    if (ans.empty()) cout << "0\n";
    else cout << ans << "\n";
    return 0;
}

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152#!/usr/bin/env python3
# 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-02 08:01
# update_at: 2026-10-02 08:50

import sys
from array import array

INF = 10**9  # 空后缀的哨兵：比 1..n 里任何值都大


def build_conflicts(a: list[int], n: int) -> tuple[list[int], array]:
    """建「不能进同一个栈」的冲突图，返回 CSR 邻接表 (start, edges)。

    存在 i<j<k 使 a[k]<a[i]<a[j] 时，a[i] 与 a[j] 连边：同栈里 a[j] 压在
    a[i] 上必须先弹，但更小的 a[k] 又排在它俩之前要先输出，a[i] 只能晚于
    a[j] 弹出，与升序输出矛盾，所以这两个值必须分进两个栈。
    最坏约 n²/2 条边，用「度数前缀和 + 回填」的 CSR 存储，内存只有 O(n+E)。
    """
    suf = [INF] * (n + 2)  # suf[j] = min(a[j..n])（下标 1..n，n+1 位是空后缀哨兵
    for i in range(n, 0, -1):
        suf[i] = min(a[i - 1], suf[i + 1])

    deg = [0] * (n + 1)  # 第一遍：数出每个值连了多少条边
    for j in range(1, n + 1):
        m = suf[j + 1]  # 位置 j 之后的最小值，即候选的 a[k]
        for i in range(1, j):
            x = a[i - 1]
            if m < x < a[j - 1]:  # a[k] < a[i] < a[j]
                deg[x] += 1
                deg[a[j - 1]] += 1

    start = [0] * (n + 2)  # 前缀和：值 u 的邻接边存放在 [start[u], start[u+1])
    for u in range(1, n + 1):
        start[u + 1] = start[u] + deg[u]

    edges = array("I", bytes(4 * start[n + 1]))
    fill = start[:]  # 第二遍：沿各自的游标回填，复用前缀和数组当游标
    for j in range(1, n + 1):
        m = suf[j + 1]
        for i in range(1, j):
            x = a[i - 1]
            if m < x < a[j - 1]:
                edges[fill[x]] = a[j - 1]
                fill[x] += 1
                edges[fill[a[j - 1]]] = x
                fill[a[j - 1]] += 1
    return start, edges


def two_color(start: list[int], edges: array, n: int, first: dict[int, int]) -> list[int]:
    """给每个值染 0/1（0 = 进 S1，1 = 进 S2）；相邻必须异色，染不上返回空列表。

    二分图每个连通块的染色整体可翻转：把「输入位置最早」的成员翻成 0，
    贪心压入时就能先出字典序更小的 a；同块其余值跟着整体翻转。
    """
    color = [-1] * (n + 1)
    for seed in range(1, n + 1):
        if color[seed] != -1:
            continue
        color[seed] = 0
        queue = [seed]
        for u in queue:  # 列表边出队边追加，块内成员都收在 queue 里
            for t in range(start[u], start[u + 1]):
                v = edges[t]
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    queue.append(v)
                elif color[v] == color[u]:
                    return []  # 奇环：两个栈怎么分工都不够用
        anchor = min(queue, key=first.__getitem__)  # 输入位置最早的成员
        if color[anchor]:  # 整块翻转，让 anchor 染 0
            for u in queue:
                color[u] ^= 1
    return color


def smallest_ops(a: list[int], n: int, color: list[int]) -> str | None:
    """贪心产出字典序最小的操作序列；凑不出 1..n 则返回 None。

    四个操作按字典序是 a<b<c<d，每一步在「当前合法的操作」里挑最小的：
    - 压入的值必须比栈顶小：把大的盖在小的上面，小的是将来的 need，
      永远轮不到弹出，这种压法一定死路，不合法；
    - 合法时先压 a——它比 b、d 都小，且「先压后弹」与「先弹后压」
      到达完全相同的状态，晚一步弹 d 不会变差；
    - 否则能弹出 need 的 b 最小（能弹 b 时压 a 必然非法），再轮到合法的 c，
      最后才是 d——b 与先压 c 再弹同样等价，c 与先弹 d 后压同样等价；
    - 输入耗尽只能弹，弹不出 need 说明这个染色救不回来。
    """
    s1: list[int] = []
    s2: list[int] = []
    ops: list[str] = []
    ptr = 0  # 下一个待压入的输入下标
    need = 1  # 下一个该输出的值
    while need <= n:
        b_now = bool(s1) and s1[-1] == need  # 此刻能否弹 b
        d_now = bool(s2) and s2[-1] == need  # 此刻能否弹 d
        if ptr == n:  # 输入耗尽，只能弹
            if b_now:
                s1.pop()
                ops.append("b")
            elif d_now:
                s2.pop()
                ops.append("d")
            else:
                return None  # 弹不出 need：这个染色方案救不回来
            need += 1
            continue

        v = a[ptr]
        push_s1 = color[v] == 0 and (not s1 or v < s1[-1])  # 染给 S1 且压入合法
        push_s2 = color[v] == 1 and (not s2 or v < s2[-1])  # 染给 S2 且压入合法
        if push_s1:  # a 最小，合法就先压
            s1.append(v)
            ops.append("a")
            ptr += 1
        elif b_now:  # 压 a 非法时 b 最小
            s1.pop()
            ops.append("b")
            need += 1
        elif push_s2:  # c 比 d 小
            s2.append(v)
            ops.append("c")
            ptr += 1
        elif d_now:  # 压 c 非法（会盖死 need），只剩 d
            s2.pop()
            ops.append("d")
            need += 1
        else:
            return None  # 无路可走：这个染色方案救不回来
    return " ".join(ops)


def solve() -> None:
    try:
        data = iter(map(int, sys.stdin.buffer.read().split()))
        n = next(data)
        a = [next(data) for _ in range(n)]
    except StopIteration:  # 输入为空或不足 n 个值，构不成 1..n 的排列
        print(0)
        return
    first = {v: i for i, v in enumerate(a)}  # 每个值在输入里的位置
    start, edges = build_conflicts(a, n)
    color = two_color(start, edges, n, first)
    ans = smallest_ops(a, n, color) if color else None
    print(ans if ans else 0)


if __name__ == "__main__":
    solve()

复杂度

时间：建图两遍枚举 $i < j$ ， $O(n^2)$ ；染色与贪心模拟各 $O(n + E)$ ，合计 $O(n^2)$ 。 $n = 1000$ 时内层判断约 $5 \times 10^5$ 次，实测远低于时限。
空间：冲突图最坏约 $\binom{n}{2}$ 条边，用「度数前缀和 + 回填」的 CSR 邻接表存储，为 $O(n + E)$ ；朴素的逐点 list 邻接表在稠密反例（如 $2\ 3\ \dots\ n\ 1$ ）上会逼近 $O(n^2)$ 的解释器开销，超出 32 MB 限制。

总结

把「不能同栈」翻译成冲突图是本题的核心：冲突条件 $\exists\, i<j<k,\ a[k]<a[i]<a[j]$ 从「小值被大值盖住」的死锁推出来，染色判定可行性，连通块按输入最早值定向保证 a 优先；模拟阶段用「压入必须递减」维持 need 永在栈顶的不变量，再按 a<b<c<d 逐步取最小合法操作，等价状态可交换保证了每步贪心都朝字典序最小走。

验证：题面 3 组样例与 15 组真实测试数据全部一致；另与「对操作序列做 BFS 求字典序最小解」的暴力对拍 $n \leqslant 6$ 全部 873 个排列、 $n = 7$ 全部 5040 个排列及 $n = 8, 9$ 共 380 组随机排列，输出逐一相同。

[NOIP2008-提高] 双栈排序

目录

形式化题目

正解

思路

代码

复杂度

总结