题解 P1750 【出栈序列】

林志杰 · 2017-05-24 17:59:48 · 题解

如果你看一下提交记录会发现有一段时间全部都是我光荣的提交记录orz...

结果最后发现错的原因是我的最小值不够大（我刚开始设置的是minn=0xffffff,最后改成0x7fffffff就对了。。。）

为了纪念这段峥嵘的碎月，发个代码庆祝一下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
stack <int> a;
int nn[10001],n,c,in=0,whe=1,i,m=0;
int main()
{
    cin>>n>>c;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&nn[i]);
    }
    while( a.size() + m < n )  { //意思是如果原序列还有值未处理 
        in=a.size();//栈内元素数量 
        int minn=0x7fffffff,wher=whe,len=c-in;
           for(i=wher;i<wher+len && i<=n;i++)
            if(nn[i]<minn) {
            whe=i;
            minn=nn[i];
               }
        if ( a.empty() || minn <= a.top() ) {//如果栈为空或者栈顶元素不是想要找的数 
            for(int i=wher;i<=whe;i++) a.push(nn[i]);//把最小元素和前面的元素压入栈 
            ++whe;//whe始终指向未处理的第一个元素 
        }
        else whe=wher;//弹出栈顶元素即可，所以应该把指针移回原位置 
        cout<<a.top()<<' ';//无论如何要输出的元素一定在栈顶 
        m++;//记录已经输出元素的数量 
        a.pop();
    }
    while(!a.empty()) {//原序列已经处理完，此时应该把栈里的元素依次弹出 
        cout<<a.top()<<' ';
        m++;
        a.pop();
    }
    return 0;
}