P1155 双栈排序题解

Comentropy · 2023-07-19 19:26:42 · 题解

~~真是一道毒瘤题。~~

如果你想要让代码可读性更强，让思路显示更清晰，可以参考鄙人的写法。

分析

Part 1

对于一个栈来说，若对于可排序列，其出栈顺序为升序，则栈中元素必定时刻保持降序（若出现特例，则考虑出栈）。

即，如果只有一个栈，则整个操作顺序是固定的：

从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。

进一步分析，将该性质移用到双栈上。

性质1：a_i，a_j 不归属于同一个栈，等价于：\exists i<j<k，使得 a_k<a_i<a_j。

这是一个很强的性质，以下为简述证明：

必要性：若存在这样的 k，则使得 a_k 一定比 a_i，a_j 先出栈，即在对 a_k 操作前，a_i，a_j 都不能弹出，否则出栈序列中将出现逆序对。这导致 a_i，a_j 同时在栈中。此时不论如何出栈都会出现逆序对，不合题意，故 a_i，a_j 不归属于同一个栈。
充分性：可以转化为以下问题：若不存在这样的 k，a_i，a_j 可以归属于同一个栈。这是显然的，因为为了保证栈的单调性，所有小于 a_j 的数已经出栈了（后面没有更小的数了，因此可以正常出栈）；所有大于 a_j 的数仍在栈底处。操作可以正确进行。

Part 2

这一部分主要是讲解输出时字典序最小的问题，有点绕。得到了上一部分的性质，则能得到每个数之间的关系，要将它们分到两个栈中，正是二分图判定问题。跑一遍染色法求解二分图即可。注意从此开始与字典序有关，尽可能先进 stk1，染色时优先染 0（0 是在 stk1 中的标志）。

之后出栈判断可以概括为：要出 stk1 就出，尽可能晚出 stk2 的元素。详细步骤如下：

对于 col=0 的元素，即要入 stk1 的元素，先对 stk1 进行检索、弹出（因为要进栈了，保证单调性）。然后如果此时 stk1 没有弹干净（没弹干净的原因见注释中对 popall 操作的说明），且 stk1_{top}<a_i，即，将要出现升序时，进行 popall 操作，清理掉比 a_i 小的所有元素。特例：见 popall 操作的说明。
对于 col=1 的元素，即要入 stk2 的元素，不要有顾虑，进行 popall 操作再进栈即可。原理是先弹 stk1 比先入 stk2 更优。

注： popall 指的是弹出所有可以弹的元素，其中遵循先弹 stk1，尽可能不弹 stk2 的规则。我们维护一个 now 来指出当前需弹的元素（序列是一个 [1,n] 的排列）。若当入要向 stk1 中压入 a_i 时，扫到 stk2_{top} = now= a_i-1，则可以等待入栈后再进行弹栈，直接退出即可。

Code

附几组关于 Part2 常见错误的数据。

#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int N=1050;
int n;
int a[N],f[N],col[N];
vector<int> e[N];
stack<int> stk1,stk2;
bool dfs(int u,int c){
    col[u]=c;
    for(int i:e[u]){
        if(col[i]==c)   return false;
        if(col[i]==-1 && !dfs(i,!c))    return false;
    }
    return true;
}
int now=1;
void popall(int lim){
    while(true){
        if(stk1.size()&&stk1.top()==now){
            stk1.pop();
            printf("b ");
            now++;
        }else if(stk2.size()&&stk2.top()==now){
            if(now==lim-1)
                break ;
            stk2.pop();
            printf("d ");
            now++;
        }else{
            // if(stk2.size())
            //     printf("\nstk=%d\n",stk2.top());
            break ;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[n+1]=n+1;
    for(int i=n;i>=1;i--)
        f[i]=min(f[i+1],a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i]<a[j]&&f[j+1]<a[i])
                e[i].push_back(j),e[j].push_back(i);
    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++){
        if(col[i]==-1&&!dfs(i,0)){
            printf("0");
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(col[i]==0){
            // 字典序问题：第一个必须出 第二个栈可以等。
            int flag=0;
            // printf("\ni=%d now=%d\n", i,now);
            while(stk1.size()&&stk1.top()==now){
                stk1.pop();
                printf("b ");
                now++,flag=1;
            }
            // printf("\ni=%d now=%d flag=%d\n",i,now,flag);
            if(stk1.size()&&stk1.top()<a[i])
                popall(a[i]);
            stk1.push(a[i]);
            printf("a ");
        }else{
            popall(0);
            stk2.push(a[i]);
            // printf("\nnew_ele=%d\n",stk2.top());
            printf("c ");
        }
    }
    popall(0);
    return 0;
}

/*
test1:
6
2 3 1 4 5 6
output: a c a b b a d b a b a b
BUG:    a c a b b a a a d 

test2:
8
1 3 4 2 7 5 8 6
output: a b a c a b b a a d b c a b b d
BUG:    a b a c a b b a d a b c a b b d 

test3:
10
10 7 8 6 3 5 4 2 1 9
ANS:    a a c a a c c a a b b b d d b b a d b b
BUG:    a a c a a c c a a b b b a d d 
*/

P1155 双栈排序 题解

分析

Part 1

Part 2

Code

P1155 双栈排序题解