AcWing 153. 双栈排序
原题链接
困难
算法
(二分图) $O(n^2)$
- 先分析单个栈,什么情况下不能成功排序?
- 如果序列是 $2 \ 3 \ 1$,用一个栈就不行,因为 $2$ 和 $3$ 必须都先进栈,然后 $1$ 才能进栈出栈。此时 $3$ 在栈顶,$2$ 出不去了。
- 形式化的,设序列为 $a$,如果在序列中存在三个位置 $i, j, k$,使得 $a_k < a_i < a_j$,那么 $i$ 和 $j$ 就构成矛盾,不能放在一个栈里面。
- 我们先预处理一下数组,找出所有矛盾的点对,然后把 $(i, j)$ 连一条边。因为我们有两个栈,只需保证 $i$ 和 $j$ 不在同一个栈里面。即预处理建图完毕以后,判断是否是二分图,如果是,就能双栈排序,否则就不能。
- 如何快读的进行预处理?设一个数组 $mi$,用 $mi[i]$ 表示 $i$ 以及 $i$ 右边的位置的最小值,那么我们从右往左预处理一遍数组,用一个 $O(n)$ 的时间可以求出来。接下来枚举 $i$ 和 $j$,去比 $mi[j + 1]$ 是不是小于 $a[i]$ 就行了。预处理建图复杂度 $O(n^2)$
- 判断可行以后,进行模拟操作输出结果。定一个变量 $cnt$,表示下一个要出的元素是几,初始是 $1$。
- 题目中规定进栈的优先级比出栈的高,所以我们先进栈,不着急出。只有进一个元素之前,发现栈顶是要出的元素的时候,才能把栈顶出栈。另外题目中规定第一个栈出栈的优先级比第二个栈出栈的优先级高,所以我们出第二个栈之前要先判断要不要出第一个栈。
- 当所有输入都处理完,再按顺序出掉两个栈里面剩余的元素。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::min;
using std::vector;
using std::queue;
using std::stack;
int n, cnt;
int a[1005];
int mi[1005];
int c[1005];
vector<int> adj[1005];
stack<int> s1, s2;
bool bfs(int u) {
c[u] = 1;
queue<int> q;
q.push(u);
while (!q.empty()) {
u = q.front();
q.pop();
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
if (c[v] == 0) {
c[v] = -c[u];
q.push(v);
}
else if (c[v] == c[u]) {
return false;
}
}
}
return true;
}
bool check() {
for (int i = 1; i <= n; ++i) {
if (c[i]) continue;
if (!bfs(i)) return false;
}
return true;
}
void work() {
cnt = 1;
for (int i = 1; i <= n; ++i) {
if (c[i] == 1) {
while (!s1.empty() && s1.top() == cnt) {
cout << "b ";
s1.pop();
cnt++;
}
cout << "a ";
s1.push(a[i]);
}
if (c[i] == -1) {
while (!s1.empty() && s1.top() == cnt) {
cout << "b ";
s1.pop();
cnt++;
}
while (!s2.empty() && s2.top() == cnt) {
cout << "d ";
s2.pop();
cnt++;
}
cout << "c ";
s2.push(a[i]);
}
}
while (!s1.empty() || !s2.empty()) {
while (!s1.empty() && s1.top() == cnt) {
cout << "b ";
s1.pop();
cnt++;
}
while (!s2.empty() && s2.top() == cnt) {
cout << "d ";
s2.pop();
cnt++;
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
mi[n] = a[n];
for (int i = n - 1; i >= 1; --i) {
mi[i] = min(mi[i + 1], a[i]);
}
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (a[i] < a[j] && mi[j + 1] < a[i]) {
// 找到一对i和j不能放在一个栈里,连边
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
if (!check()) cout << "0\n";
else work();
return 0;
}