[数据结构与算法]Daimayuan Online Judge 出栈序列判断

代码源每日一题

现在有一个栈，有nn个元素，分别为1,2,…,n1,2,…,n。我们可以通过push和pop操作，将这nn个元素依次放入栈中，然后从栈中弹出，依次把栈里面的元素写下来得到的序列就是出栈序列。

比如n=3n=3，如果执行push 1, push 2, pop, push 3, pop, pop，那么我们pop操作得到的元素依次是2,3,12,3,1。也就是出栈序列就是2,3,12,3,1。

现在给定一个合法的出栈序列，请输出一个合法的由push和pop操作构成的出栈序列。这里要求push操作一定是按1,2,…,n1,2,…,n的顺序。

输入格式

第一行一个整数nn，接下来一行nn个整数，表示出栈序列。

输出格式

输出2n2n行，每行一个push x或pop的操作，可以发现一个出现序列对应的操作序列是唯一的。

样例输入1

3
2 3 1

样例输出1

push 1
push 2
pop
push 3
pop
pop

样例输入2

5
1 3 5 4 2

样例输出2

push 1
pop
push 2
push 3
pop
push 4
push 5
pop
pop
pop

数据规模

对于100%100%的数据，保证1≤n≤1000001≤n≤100000，出栈序列一定是个合法的出栈序列。

中文

思路：这个题是模拟栈的进栈与出栈，可以通过观察样例的大小的变化发现：前一个数小于当前数，那么它就一定是进栈，因为题目要求是从1到n按顺序插入的，而小的数先弹出就说明大的数还没有进。然后是前一个数大于当前数，那么当前数就一定是出栈的，因为之前插入过了，但是这里需要注意弹出栈也是有顺序的，你不能先弹出1，在弹出2，所以弹出的数一定是当前最大的，也就相当于栈顶。数据范围问题：是1e5,最后输出的东西的个数会是2e5，这里用cout即使是取消缓存仍然会非常慢，所以用printf。（我就是在这里被卡了）

完整代码：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
//#define int long long
#define fir first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define repd(i, l, r) for (int i = l; i >= r; --i)
#define pb push_back


const int N=1e5+10;
int a[N];
stack<int>sta;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    scanf("%d",&n);
    int k=1;
    sta.push(0);
    int x;
    rep(i,1,n)
    {
        scanf("%d",&x);
        while(x!=sta.top())
        {
            sta.push(k++);
            printf("push %d\n",sta.top());
        }
        printf("pop\n");
        sta.pop();
    }
    return 0;
}