洛谷1155 [NOIP2008]双栈排序

题意

用两个栈进行排序，只有入栈和出栈操作，求字典序最小的操作序列。如果无法排序输出 No 。

数列长度 $N\le 1000$ 。

题解

先考虑单栈排序。如果存在 $i < j < k$ 但 $S_k < S_i < S_j$ 就无法进行排序。

这道题有两个栈，可以对所有矛盾关系 $(i,j)$ 建边，然后跑一遍 $\text{dfs}$ 进行染色，判断是否有矛盾。

枚举所有的 $(i,j)$ 可以使用 $\text{DP}$ 优化。用 $F_k$ 表示 $[k,n]$ 中最小的数，那么每次判断 $S_i<S_j \ \mathrm{\&\&} \ F_{j+1} < S_i$ 就行了。

染色后每个数属于哪个栈就已知了，要使字典序最小，那么第一个数应进入第一个栈，剩下的按顺序模拟就行了。最后还要把栈中剩余的数输出。

UPD:20190704 代码已更新

去做了CH上的这道题，发现WA了。看数据发现全部累积到最后出栈会使得一些数无序，所以应该在入栈过程中把栈顶是当前数的情况全部处理完。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[1000005];
stack <int> x,y;
int cnt,head[1005],n,s[1005],f[1005],col[1005],now;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int cur)
{
    col[x]=cur;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (col[y]==-1) dfs(y,cur^1);
        else if (col[y]!=(cur^1)) { printf("0"); exit(0); }
    }
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    f[n+1]=1e9;
    for (int i=n;i;i--) f[i]=min(f[i+1],s[i]);
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            if (s[i]>=s[j] || s[i]<=f[j+1]) continue;
            add(i,j);
            add(j,i);
        }
    }
    memset(col,-1,sizeof(col));
    for (int i=1;i<=n;i++)
    {
        if (~col[i]) continue;
        dfs(i,0);
    }
    now=1;
    for (int i=1;i<=n;i++)
    {
        if (!col[i])
        {
            x.push(s[i]);
            printf("a ");
        }
        else
        {
            y.push(s[i]);
            printf("c ");
        }
        while ((!x.empty() && x.top()==now) || (!y.empty() && y.top()==now))
        {
            if (!x.empty() && x.top()==now)
            {
                x.pop();
                now++;
                printf("b ");
            }
            else
            {
                y.pop();
                now++;
                printf("d ");
            }
        }
    }
    return 0;
}