题目描述

Tom最近在研究一个有趣的排序问题。如图所示,通过2个栈S1和S2,Tom希望借助以下4种操作实现将输入序列升序排序。


操作a:如果输入序列不为空,将第一个元素压入栈S1

操作b:如果栈S1不为空,将S1栈顶元素弹出至输出序列

操作c:如果输入序列不为空,将第一个元素压入栈S2

操作d:如果栈S2不为空,将S2栈顶元素弹出至输出序列

如果一个1~n的排列P可以通过一系列操作使得输出序列为1,2,…,(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希望知道其中字典序最小的操作序列是什么。

输入描述:

第一行是一个整数n。
第二行有n个用空格隔开的正整数,构成一个1~n的排列

输出描述:

共一行,如果输入的排列不是“可双栈排序排列”,输出数字0;否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

示例1

输入
4
1 3 2 4
输出
a b a a b b a b

示例2

输入
4
2 3 4 1
输出
0

示例3

输入
3
2 3 1
输出
a c a b b d

备注

30%的数据满足:
50%的数据满足:
100%的数据满足:

解答

这题我一开始想的是贪心。但后来发现a和c的入栈顺序有误可能会导致无解。

然后我看了一下标签——“图论”?嗯???

我看了几个题解。二分图。i与j不能放在一起。贪心。

然后我再试着打了打代码,A了,证明我的思路是正确的。感谢那些题解提供的帮助,虽然我没有完全看懂。

这是一道很巧妙的题目,用了一个我认为很重要的思想。

思路零(最开始的思路)

经过了一些考虑的贪心。

第一,我们如果入这个栈的数是目前排序到的最大的数+1,那么这个栈我们是不是不能再入栈?这是显然的,在这个栈的下一次进栈前,我们应当将这个元素出栈。

第二,否则能入栈则入栈,尽量入a栈。

第三,栈顶的元素必须比入栈的元素要大,正确性显然。

考虑执行顺序b->a->d->c。检查到这种操作能执行则执行。显然这种执行顺序在贪心的求字典序最小上是正确的。

然后这个贪心当然是错误的啦

思路一(来自某题解)

我们先考虑一个栈能不能排。如果一个栈能排的话我们还会用两个栈吗?按照贪心原则,这么做肯定是不行的。

那么问题来了——什么时候我们得必须用两个栈才能排?

引理(来自同样的题解和另一个题解)

在排列P中。若P[k]<P[i]<P[j],i<j<k,则i和j不能在同一个栈中。正确性不是很显然,感性理解也是可以的。证明可以去网上找其它的题解。想要理解的话不如自己拿个例子试试,比如(2,3,1)。

思路二(来自某题解)

这道题到底跟图论有什么关系?最大的关系在于“双”这个字。

二分图可以用来表示关系的冲突。比如两个相邻的点不能染成同样的颜色,又或是两个数不能放进同一个栈中。知道了这个关系,我们可以知道两个数应该放在什么栈里,知道到底存不存在方案使得排序完成。

我们将这道题转换成二分图进行处理。

枚举i<j<ni<j<n,若j+1~n中存在k使得P[k]<P[i]<P[j]P[k]<P[i]<P[j],则i和j连一条边,代表他们不能入同一个栈。

显然若i与j没有连边,就代表他们按顺序排始终可以出现在同一个栈中。

这个过程可以用一个后缀求最小值来O(n2)O(n2)地求得。

改进后的贪心思路(建立在求得的二分图的基础上)

显然我们现在将图染成了两种颜色。若颜色不同则代表它得入不同的栈。

那么我们考虑一下,顺序是ABC,A是0,B是1,C是0。那么AC肯定入a栈,B入c栈对不对?因为A是最先的。在操作顺序aca和cac中,我们选择前一个操作更好。所以我们可以得到颜色与第一个数同色的点入a栈,其余入c栈。

在入栈的基础上,我们再使用上方的贪心模拟,按照b->a->d->c的操作顺序考虑。显然这种顺序是最优的。并且根据得到的二分图入栈,可以保证顺序是正确的。保证顺序正确得到可行解的同时字典序最小,那么就是题目要求得的解。

何为无解的情况?就是无法构造二分图的情况。即A-B B-C C-A的情况(A-B:A不能和B放在一起)。

个人觉得这题是道很好的拓宽思路的题目2333

Code

#include<bits/stdc++.h>
using namespace std;

const int N=1010,M=200010;
int P[N];

int h[N],to[M],nexp[M],p=1;
inline void ins(int a,int b){
    nexp[p]=h[a],h[a]=p,to[p]=b,p++;
}

int sm[N];
int color[N];
bool imp;
void dfs(int x,int c){
    color[x]=c;
    for(int u=h[x];!imp && u;u=nexp[u]){
        if(color[to[u]]==-1) dfs(to[u],c^1);
        else if(color[x]==color[to[u]]) imp=true;
    }
}

int s1[N],t1=1;
int s2[N],t2=1;
int now;

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>P[i];
    sm[n]=P[n];
    for(int i=n-1;i>=1;i--) sm[i]=min(sm[i+1],P[i]); // 后缀最小值
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<n;j++)
            if(sm[j+1]<P[i]&&P[i]<P[j]) ins(i,j),ins(j,i); // 建图
    memset(color,-1,sizeof(color));
    for(int i=1;i<=n;i++){
        if(color[i]==-1) dfs(i,0); // 进行染色
        if(imp) printf("0\n"),exit(0); // 无解则退出
    }
    int i=1;
    now=1;
    while(now<=n){
        if(s1[t1-1]==now)t1--,now++,printf("b ");
        else if(color[i]==0)s1[t1++]=P[i++],printf("a ");
        else if(s2[t2-1]==now)t2--,now++,printf("d ");
        else if(color[i]==1)s2[t2++]=P[i++],printf("c ");
    } // 进行贪心的模拟
    return 0;
}


来源:ACX