[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
全部评论
#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

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务