【每日一题】8月7日题目精讲—双栈排序

题号 NC16616
名称双栈排序
来源 NOIP历年真题练习-提高组
 戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

菜鸡还没学二分图。。。
题意：
给定一个序列，问能否双栈排序，如果能，请输出字典序最小的方案；
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c：如果输入序列不为空，将第一个元素压入栈S2
操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列
题解：
题目让以字典序最小的顺序输出，那么这样的话我们操作顺序直接以abcd来操作即可。
对于一个数，我们应该把他放进栈a呢，还是放进栈b呢。
因为字典序最小，所以我们如果能放进栈a实现这些操作，那么我们必然不会把他放进栈b实现这个操作。

我们先考虑一个栈的情况。
如果序列是 3 1 4 2 5
不难看出，这个如果只有一个栈的情况下，这个是无法完成题目要求的。分析一下。
3（3入栈）
3 1 （1入栈）
3 （1出栈）
3 4 （4入栈）？？？
仿佛出了点问题，3还没出来呢，4怎么能进去呢。。但是4不进去，2也进不去啊，（仿佛出现了混乱
从这里可以发现一个规律

栈顶元素一定要小于栈内元素，若当前最小值还未入栈, 那么这个栈一定不能弹, 只能一直加, 直到最小值入栈, 那么在这个过程中, 就有可能出现冲突。
但是这里用的是两个栈，如果这个a栈不能放，我们可以先把元素放到b栈过度一下。

对于两个栈来讲，如果能放进a栈的话，我们就不要把他放进b栈，所以放a栈的时候我们需要特判一下，这个元素到底能不能放进a栈，如果放进去后面会不会产生冲突。

首先我们要满足一点，就是栈顶元素要小于栈内元素

(la.empty()||la.top()>a[cnt])

第二点我们要检查一下之后的序列会不会导致把元素放进a栈后误解，如果是这样，我们尝试放入b栈

也就是这个check函数，如果栈b为空，那么我们可以用b栈作为一个辅助栈，肯定可以。
然后我么做只有一个栈的时候的检查，也就是若当前最小值还未入栈, 那么这个栈一定不能弹, 只能一直加, 直到最小值入栈, 那么在这个过程中, 就有可能出现冲突。但是在这个条件下，不要忘记还有b栈可以辅助，如果后面元素大于栈顶，但是小于b栈的顶元素，那么我们可以暂时放到b栈中，两者可以交替用。
如果都大于的话，那么我们就要考虑 从这个位置之后的数，有没有小于当前位置的，如果小于，只能返回false了，因为b栈也被用过了，这里联想一下一个栈的情况，这两个栈后面不能有比当前栈顶元素都小的元素了，如果出现，就会发生上面所说的混乱，也就是前面标黑的那一段话。
为什么要从break后面的位置来找有没有比当前栈顶小的数，因为如果数都比栈顶大的话，栈顶元素就会在到达那个最大元素的位置时被抛出，所以没有影响！！如果那个位置之后有小于栈顶的数，那就产生冲突了
（不如拿笔尝试一下这组数据）10 2 8 1 7 9 3 4 5 6

bool check(int pos){
    if(lb.empty()) return true;
    int i;
    for(i=pos+1;i<=n;i++) if(a[i]>a[pos]&&a[i]>lb.top()) break;
    for(int j=i+1;j<=n;j++) if(a[j]<a[pos]) return false;
    return true;
}

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define endl '\n'
#define ios std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
//#define int long long
const int maxn = 1e4+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;

int a[maxn];
vector<int> ans;
vector<char> now;
stack<int> la,lb;
int n;
bool check(int pos){
    if(lb.empty()) return true;
    int i;
    for(i=pos+1;i<=n;i++) if(a[i]>a[pos]&&a[i]>lb.top()) break;
    for(int j=i+1;j<=n;j++) if(a[j]<a[pos]) return false;
    return true;
}
int main(){

    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    bool flag;
    int cnt=1;
    //cout<<555<<endl;
    ans.push_back(0);
    for(int i=1;i<=n*2;i++){
        flag=false;
        //cout<<555<<endl;
        if((la.empty()||la.top()>a[cnt])&&cnt<=n&&check(cnt)){
            la.push(a[cnt]);
            flag=true;
            cnt++;
            now.push_back('a');
        }
        else if(!la.empty()&&ans.back()+1==la.top()){
            ans.push_back(la.top());
            la.pop();
            flag=true;
            now.push_back('b');
        }
        else if((lb.empty()||lb.top()>a[cnt])&&cnt<=n){
            lb.push(a[cnt]);
            flag=true;
            cnt++;
            now.push_back('c');
        }
        else if(!lb.empty()&&ans.back()+1==lb.top()){
            ans.push_back(lb.top());
            lb.pop();
            flag=true;
            now.push_back('d');
        }
        if(!flag) break;
        //cout<<cnt<<endl;
//        for(auto it : ans) cout<<it<<" ";
//        cout<<endl;
//        for(auto it : now) cout<<it<<" ";
//        cout<<endl;
    }
    if(!flag) cout<<0<<endl;
    else for(auto it : now) cout<<it<<" ";
    return 0;

}

感谢@Haut－张承树同学提供的题解，奖励牛币100已发放～
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

【每日一题】8月7日题目精讲—双栈排序

题解

活动奖励：

牛客博客开通方式

全站热榜