LG1155【NOIp2008】双栈排序 <二分图染色>

Problem

【NOIp2008】双栈排序

题目描述

$Tom$最近在研究一个有趣的排序问题。如图所示，通过$2$个栈$S_1$和$S_2$，$Tom$希望借助以下$4$种操作实现将输入序列升序排序。
操作$a$: 如果输入序列不为空，将第一个元素压入栈$S_1$
操作$b$: 如果栈$S_1$不为空，将$S_1$栈顶元素弹出至输出序列
操作$c$: 如果输入序列不为空，将第一个元素压入栈$S_2$
操作$d$: 如果栈$S_2$不为空，将$S_2$栈顶元素弹出至输出序列
如果一个$1\sim n$的排列$P$可以通过一系列操作使得输出序列为$1,2,\cdots(n-1),n$，$Tom$就称$P$是一个“可双栈排序排列”。例如$(1,3,2,4)$就是一个“可双栈排序序列”，而$(2,3,4,1)$不是。下图描述了一个将$(1,3,2,4)$排序的操作序列：$<a,c,c,b,a,d,d,b>$


当然，这样的操作序列有可能有几个，对于上例$(1,3,2,4)$，$<a,c,c,b,a,d,d,b>$是另外一个可行的操作序列。$Tom$希望知道其中字典序最小的操作序列是什么。

输入输出格式

输入格式：
输入文件$twostack.in$的第一行是一个整数$n$。
第二行有$n$个用空格隔开的正整数，构成一个$1\sim n$的排列。
输出格式：
输出文件$twostack.out$共一行，如果输入的排列不是“可双栈排序排列”，输出数字$0$；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

输入输出样例

输入样例#1

4
1 3 2 4

输出样例#1

a b a a b b a b

输入样例#2

4
2 3 4 1

输出样例#2

0

输入样例#3

3
2 3 1

输出样例#3

a c a b b d

说明

$30\%$的数据满足： $n\le10$
$50\%$的数据满足： $n\le 50$
$100\%$的数据满足： $n\le 1000$

标签：二分图染色

Solution

一道很有意思的联赛题。
对于任意两数$i,j,k$，若有$i<j<k,a_k<a_i<a_j$，为了使$a_k$最先出栈，那么$a_i$和$a_j$一定在$a_k$之后出栈，若顺次放进同一个栈，那么$a_j$必然在$a_i$之前出栈，不满足题意。因此遇到这种情况$a_i$和$a_j$一定分别放入两个栈中。
据此，只要存在$i<j<k$，有$a_k<a_i<a_j$，那么$a_i$和$a_j$一定在不同栈中。这样就构成了一个二分图。
扫描一遍，确定那些数对不能在同一栈中，确定互斥关系。若不能构成二分图，那么就不可排序。否则在判断过程中染色，确定不同数在哪个栈中，模拟排序过程，每次等到当前排到的数进栈后把能出栈的都出栈。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
using namespace std;
vector <int> G[MAX_N+5];
int n, a[MAX_N+5], mi[MAX_N+5], col[MAX_N+5];
void DFS(int u) {
    for (auto v : G[u]) {
        if (!col[v])	col[v] = -col[u], DFS(v);
        if (col[u] == col[v]) {puts("0");	exit(0);}
    }
}
void prt() {
    int cur = 1;	stack <int> sa, sb;
    for (int i = 1; i <= n; i++) {
        if (col[i] == 1)	putchar('a'), putchar(' '), sa.push(a[i]);
        else	putchar('c'), putchar(' '), sb.push(a[i]);
        for (; !sa.empty() && sa.top() == cur; sa.pop(), cur++)	putchar('b'), putchar(' ');
        for (; !sb.empty() && sb.top() == cur; sb.pop(), cur++)	putchar('d'), putchar(' ');
        for (; !sa.empty() && sa.top() == cur; sa.pop(), cur++)	putchar('b'), putchar(' ');
    }
}
int main() {
    scanf("%d", &n);	for (int i = 1; i <= n; i++)	scanf("%d", a+i);
    mi[n+1] = 0x3f3f3f3f;	for (int i = n; i; i--)	mi[i] = min(a[i], mi[i+1]);
    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])	G[i].push_back(j), G[j].push_back(i);
    for (int i = 1; i <= n; i++)	if (!col[i])	col[i] = 1, DFS(i);	prt();
    return 0;
}