目录一、题目1、题目描述2、输入输出2.1输入2.2输出3、原题链接二、解题报告1、思路分析2、复杂度3、代码详解一、题目1、题目描述2、输入输出2.1输入2.2输出3、原题链接https://www.luogu.com.cn/problem/P1155二、解题报告1、思路分析先考虑单栈怎么做如果 i j, p[i] p[j]那么 p[i] 要先比 p[j] 出栈但如果 存在 k j 并且 p[k] p[i]就无法单栈排序了这是2026年408数据结构大题T2沟槽的408还在追我也就是说当出现 i j kp[k] p[i] p[j]那么单栈无法排序必须将三个数放入两个栈、考虑到答案要操作序列字典序最小我们尽可能让操作a在靠前的位置做那么 p[i] 进入栈1操作ap[j] 就必须进入栈2(操作c)那么p[k] 就要进入栈1操作a来保证操作序列最小预处理suf[i] 代表 [i..n - 1] 的最小值也就是说我们可以按照从小到大的方式遍历下标i然后枚举j如果存在suf[j 1] p[i] p[j]那么我们将i, j 连边然后跑二分图染色如果是二分图那么一定可双栈排序否则不能然后我们染完色后遍历 p[1] ~ p[n]如果p[i] 属于栈1那么我们弹出所有栈1比p[i] 小的数入栈即可属于栈2类似2、复杂度时间复杂度O(N) 空间复杂度O(N)3、代码详解​#include bits/stdc.h namespace ranges std::ranges; namespace views std::views; using i64 long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin n; std::vectorint p(n); for (int i 0; i n; i) { std::cin p[i]; --p[i]; } std::vectorint suf(n); for (int i n - 1; i 0; --i) { suf[i] p[i]; if (i 1 n) { suf[i] std::min(suf[i], suf[i 1]); } } std::vectorstd::vectorint adj(n); for (int i 0; i n; i) { for (int j i 1; j 1 n; j) { if (p[i] p[j] p[i] suf[j 1]) { adj[i].push_back(j); adj[j].push_back(i); } } } std::vectorint col(n); std::queueint q; for (int i 0; i n; i) { if (col[i] 0) { continue; } col[i] 1; q.push(i); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (col[v] 0) { col[v] 3 - col[u]; q.push(v); } else if (col[v] col[u] ! 3) { std::cout 0 \n; return 0; } } } } std::stackint stk1, stk2; std::vectorchar ans; int cur 0; for (int i 0; i n; ) { if (col[i] 1 (stk1.empty() || p[i] stk1.top())) { stk1.push(p[i]); ans.push_back(a); } else if (!stk1.empty() stk1.top() cur) { stk1.pop(); ans.push_back(b); cur; } else if (col[i] 2 (stk2.empty() || p[i] stk2.top())) { stk2.push(p[i]); ans.push_back(c); } else if (!stk2.empty() stk2.top() cur) { stk2.pop(); ans.push_back(d); cur; } } while (!stk1.empty() || !stk2.empty()) { if (!stk1.empty() stk1.top() cur) { stk1.pop(); ans.push_back(b); cur; } else { assert(!stk2.empty() stk2.top() cur); stk2.pop(); ans.push_back(d); cur; } } for (int i 0; i 2 * n; i) { std::cout ans[i] \n[i 1 2 * n]; } return 0; }