[PAT解题报告] Pop Sequence

简单题，给定入栈顺序是1-n，再给一个出栈顺序，多了一个条件，堆栈的最大容量给定，问是否可能达到这个出栈队列。

分析：直接用一个堆栈模拟。假设我们现在考虑1..(i -1)都进入了堆栈，i还没有进入堆栈。

我们一个一个元素考虑出栈序列的元素x：

考虑两种情况：

(1) i > x

这时x入过堆栈了。

(1.1) 如果它不是堆栈顶，我们无法pop出x了——后面再怎么入栈都无法第一个弹出x，这不可能。

(1.2) 如果x是堆栈顶，直接从堆栈pop就可以了，处理下一个出栈元素。

(2) i <= x

这时x还没有入栈，要想让x出栈，我们必须把从i到x都压入堆栈，这时x在顶端，pop出来即可。但是要注意，压入这么多元素要保证堆栈里面元素的个数不超过给定的堆栈容量，否则也是不可能。

总之，细致处理这两种情况，用堆栈模拟即可。

代码：

#include <stack>
#include <cstdio>
using namespace std;

int main() {
int m,n,k;

    for (scanf("%d%d%d",&m,&n,&k);k;--k) {
        bool can = true;
        stack<int> s;
        for (int i = 1, j = 0; j < n; ++j) {
            int x;
            scanf("%d",&x);
            if (can) {
                if (i > x) {
                    if (s.empty() || (s.top() != x)) {
                        can = false;
                    }
                    else {
                        s.pop();
                    }
                }
                else {
                    for (;(i <= x) && (i <= n) && (s.size() <= m); ++i) {
                        s.push(i);
                    }
                    if ((!s.empty()) && (s.size() <= m) && (s.top() == x)) {
                        s.pop();
                    }
                    else {
                        can = false;
                    }
                }
            
            }
        }
        puts(can?"YES":"NO");
    }
    return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1051

全部评论

推荐最新楼层

早起的鸟儿很好吃

浙江大学 Java

#include<cstdio> #include<stack> using namespace std; stack<int> st; int main() { int m, n, k; scanf("%d%d%d", &m, &n, &k); while (k--) { int t = n; int num = 1; bool flag = true; while (t--) { int x; scanf("%d", &x); while(num<=x) st.push(num++); int last = st.top(); if (last != x|| st.size() > m) flag = false; st.pop(); } if (flag) printf("YES\n"); else printf("NO\n"); } return 0; }

送花回复分享

发布于 2017-07-28 09:27