二分图思想
DuskLight
·
·
题解
应用原理：
因为有AB两个栈，要升序输出，则一定满足：
所以我们将需要一份判断任意两元素是否在同一线性结构中的问题。
很好想到：**二分图**
完整代码如下，注释详细，~~码风就凑合看吧。~~
```
#include <bits/stdc++.h>
#define M 1005
using namespace std;
int n,a[M],minx[M],now=1;
short color[M];
vector<int>edge[M];
stack<int>s1,s2;
bool dfs(int now,int go,int c)
{
color[now]=c; //c=1为黑，-1为白，二分图用双色即可
for (int i=0;i<edge[now].size();i++)
{
int next=edge[now][i];
if (next==go)continue;
if (color[next]==c) return 0;
if (!color[next]&&!dfs(next,now,-c))return 0;
}
return 1;
}
bool check(int col) //判断需要弹出的值是否是当前栈顶值
{
if (col==1)
{
if (!s1.empty()&&s1.top()==now)return 1; //是就优先弹出
}
else
{
if (!s2.empty()&&s2.top()==now)return 1;
}
return 0;
}
void print(int col) //进入输出队列
{
now++; //假设弹出3后，下一个需要弹出4，所以+1.
if (col==1)
{
printf("b ");s1.pop();
}
else
{
printf("d ");s2.pop();
}
}
void chain(int need,int c){
if(c==1){
while(!s1.empty()&&s1.top()<need) {//栈中只能放更小的值
if(check(1)) print(1);
else print(-1);
}
s1.push(need);
}
else{
while(check(1))print(1); //能弹就弹
while(!s2.empty()&&s2.top()<need)
{
if (check(1))print(1);
else print(-1);
}
while(check(1))print(1);
s2.push(need);
}
if (c==1)printf("a "); //颜色为1就压入A栈，如果是染过色的（有冲突的）
else printf("c "); //就压入B栈
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
minx[n+1]=n+1;
for (int i=n;i>0;i--)
{
minx[i]=min(minx[i+1],a[i]); //储存每个点右侧的最小值
}
for (int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++){
if(a[i]<a[j]&&a[i]>minx[j]){ //如果一个点小于右侧某点，且大于右侧某点更右侧的一个点
edge[i].push_back(j); //则有冲突不成立，所以存放入一个二分图中
//如果存在一个k<i<j的点且a[k]<a[i]且a[k]>a[i]的点。那么必须满足a[k]于a[i]不在同栈
//！！！详解：如果存在a[k]>a[i]，那么i必须先进入输出队列，所以a[k]不能先弹出，只能和a[j]异栈
//所以需要二分图判定是否可能为同栈.
edge[j].push_back(i); //把有冲突的 点放在一个二分图中
}
}
}
for (int i=1;i<=n;i++)
{
if (!color[i])
{
if (!dfs(i,0,1))
{
printf("0");
return 0; //二分图判定
}
}
}
// 判断能否联通
for(int i=1;i<=n;i++){
chain(a[i],color[i]);
}
while(!s1.empty())
{
if (check(1))print(1);
else print(-1);
}
while(!s2.empty())print(-1);
return 0;
}
```