【二分图+栈排序】题解：P1155 [NOIP2008 提高组] 双栈排序_二分图染色_贪心_模拟_C++算法竞赛

文章目录P1155 [NOIP2008 提高组] 双栈排序题解P1155 [NOIP2008 提高组] 双栈排序题目描述Tom 最近在研究一个有趣的排序问题。如图所示通过2 22个栈S 1 S_1S1​和S 2 S_2S2​Tom 希望借助以下4 44种操作实现将输入序列升序排序。操作a \verb!a!a将第一个元素压入栈S 1 S_1S1​。操作b \verb!b!b将S 1 S_1S1​栈顶元素弹出至输出序列。操作c \verb!c!c将第一个元素压入栈S 2 S_2S2​。操作d \verb!d!d将S 2 S_2S2​栈顶元素弹出至输出序列。如果一个1 ∼ n 1\sim n1∼n的排列P PP可以通过一系列合法操作使得输出序列为( 1 , 2 , ⋯ , n − 1 , n ) (1,2,\cdots,n-1,n)(1,2,⋯,n−1,n)Tom 就称P PP是一个“可双栈排序排列”。例如( 1 , 3 , 2 , 4 ) (1,3,2,4)(1,3,2,4)就是一个“可双栈排序序列”而( 2 , 3 , 4 , 1 ) (2,3,4,1)(2,3,4,1)不是。下图描述了一个将( 1 , 3 , 2 , 4 ) (1,3,2,4)(1,3,2,4)排序的操作序列a,c,c,b,a,d,d,b \texttt {a,c,c,b,a,d,d,b}a,c,c,b,a,d,d,b。当然这样的操作序列有可能有几个对于上例( 1 , 3 , 2 , 4 ) (1,3,2,4)(1,3,2,4)a,b,a,a,b,b,a,b \texttt{a,b,a,a,b,b,a,b}a,b,a,a,b,b,a,b是另外一个可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。输入格式第一行是一个整数n nn。第二行有n nn个用空格隔开的正整数构成一个1 ∼ n 1\sim n1∼n的排列。输出格式共一行如果输入的排列不是“可双栈排序排列”输出0。否则输出字典序最小的操作序列每两个操作之间用空格隔开行尾没有空格。样例 #1样例输入 #14 1 3 2 4样例输出 #1a b a a b b a b样例 #2样例输入 #24 2 3 4 1样例输出 #20样例 #3样例输入 #33 2 3 1样例输出 #3a c a b b d提示30 % 30\%30%的数据满足n ≤ 10 n\le10n≤10。50 % 50\%50%的数据满足n ≤ 50 n\le50n≤50。100 % 100\%100%的数据满足n ≤ 1000 n\le1000n≤1000。2021.06.17 加强 by SSerxhs。hack 数据单独分为一个 subtask 防止混淆。noip2008 提高第四题题解这道题有难度。遇到这种题我们先找规律假设只有一个栈那满足什么条件的序列无法成功排序呢尝试一下1,2,3的所有排列中只有2,3,1不行。1,2,3,4的所有排列中1,3,4,2不行我们只看[2,3,1]和[3,4,2]不难找到一个共性若a[i],a[j],a[k]满足ijk且a[i]a[j],a[i]a[k]则无法完成单栈排序简单证明这样的话会使较大的a[j]压在较小的a[i]上且a[k]无法在a[i]之前出栈。所以一定会造成矛盾的情况。考虑如何判断数字冲突三层循环太费时间可以只枚举(i,j)对于a[k]预处理一个后缀最小值Min。若a[i]Min[j1]则后面一定有一个或若干个不满足条件的a[k]所以这就是需要双栈排序的原因了。那么我们要思考一个问题哪些数字要进入第一个栈哪些数字要进入第二个栈很明显就是冲突了的那些数字只有让那些数字不进入同一个栈才有成功排序的可能。我们很自然地就会想到——二分图染色。对于每一对a[i],a[j]建一条无向边然后对图进行二分图判定染色如果能成功染色则说明有合法的方案反之则不能接下来可以通过用两个栈模拟的方式求出操作步骤。比较难以解释详见代码然后题目的另一个难点出现了要求操作字典序最小压入第一个栈弹出第一个栈压入第二个栈弹出第二个栈我们肯定要对每个处理步骤一顿贪心。我们假设染色时染成0要进入第一个栈染成1要进入第二个栈对于二分图染色判断从小到大枚举所有的点并且在进行染色时以0开始。这样染完色之后序号较小的一定会进入第一个栈减小字典序然后模拟时对于字典序小的操作优先做。即能先做a就先做a再能先做b就先做b这里还有一个坑点假设S1[7,5],S2[8,6]我们要把9放入栈S1中正常第一眼想到的方案是先把所有9的都弹栈再把9放入S1序列bdbda但这是错的最优的方案是当7弹栈后就把9放入栈S1中这样会节省字典序序列bdbad也就是说假设要把x放入栈St那么只要满足 St为空 或 St.top()x此时就直接把x压入栈中这样是最优的模拟还有一些细节见代码#includebits/stdc.husingnamespacestd;constintmaxn1005;intn,a[maxn],Min[maxn];// Min是a的后缀最小值vectorintG[maxn];intcol[maxn];// 二分图染色数组intdfs(intu,intc){col[u]c;for(intv:G[u]){if(col[v]c)return0;if(col[v]-1dfs(v,c^1)0)return0;}return1;}voidsolve(){cinn;for(inti1;in;i)cina[i];// 求后缀最小值Min[n]a[n];// 初始化for(intin-1;i1;i--){Min[i]min(Min[i1],a[i]);}// 判断是否存在三元组(a[i],a[j],a[k])满足ijk且a[i]a[j],a[i]a[k]a[k]可以利用后缀最小值来检查for(inti1;in;i){for(intji1;jn-1;j){if(a[i]a[j]a[i]Min[j1]){// 因为jk所以a[k]要取Min[j1]G[i].push_back(j);// 建边准备跑二分图染色G[j].push_back(i);// 如果两个点有边相连则它们一定不能放在同一个栈中}}}memset(col,-1,sizeofcol);// 初始化染色数组为-1boolflagtrue;// 能否成功二分图染色for(inti1;in;i){// 按照下标从小到大遍历这样序号小的一定先染上0保证字典序最小if(col[i]-1dfs(i,0)0)flagfalse;}// 如果不是二分图的话说明不能成功匹配就可以直接返回了if(!flag){cout0\n;return;}// 然后大模拟 染色结束后染0的点一定入栈1染1的点一定入栈2stackintS[3];// S[1],S[2]表示两个栈intpos1;// pos表示当前该放哪个数for(inti1;inposn;i){// 循环当前要把哪个数入栈if(col[i]0){// 应该放入第一个栈while(posa[i]){// 在while里面要注意按照字典序进行操作即操作序号字典序小的先操作这样保证输出的答案字典序最小if(S[1].empty()||S[1].top()a[i]){// 这样就可以直接把a[i]放入栈并退出循环// 这是节省字典序的方法一定要注意这个细节S[1].push(a[i]);couta ;break;}// 下面的操作是为了弹出pos让a[i]早点入栈elseif(!S[1].empty()S[1].top()pos){// 注意判栈空的情况S[1].pop();coutb ;pos;}elseif(!S[2].empty()S[2].top()pos){S[2].pop();coutd ;pos;}}}else{// 放入栈1同理while(posa[i]){if(!S[1].empty()S[1].top()pos){S[1].pop();coutb ;pos;}elseif(S[2].empty()||S[2].top()a[i]){S[2].push(a[i]);coutc ;break;}elseif(!S[2].empty()S[2].top()pos){S[2].pop();coutd ;pos;}}}}// 最后如果栈中还有剩余的元素就继续弹栈。// 因为此时两个栈里已经排好序从栈顶到栈底所以只要按照大小关系输出即可while(S[1].size()||S[2].size()){if(S[2].empty()){S[1].pop();coutb ;}elseif(S[1].empty()){S[2].pop();coutd ;}elseif(S[1].top()S[2].top()){S[1].pop();coutb ;}elseif(S[1].top()S[2].top()){S[2].pop();coutd ;}}}signedmain(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);solve();return0;}