Luogu P1750 【出栈序列】

一眼(万年)贪心
minn设小调不出来祭

首先要保证更靠前的输出更小
那么容易想到，对于之后可能入栈的元素（即栈的剩余空间仍能装下的所有元素），我们可以取其中的最小值minn，和栈顶元素$top$比较
，如果minn<top我们将minn及之前的所有元素入栈，然后输出minn并且让它出栈，当然可以直接输出不入栈，这是次要的，
否则一直弹出栈顶直到栈空或top>minn

#include<iostream>

#include<cstdio>

#include<stack>

using namespace std;

const int maxn=;

int n,c,a[maxn],rest,pos;

stack<int>st;

int main()

{

    scanf("%d%d",&n,&c);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

    rest=c,pos=;    //rest表示剩余可用栈空间，pos表示第一个未处理元素的位置

    while(pos!=n+)        //元素没有全被处理

    {

        int minn=2e9,r;        //minn记录可能入栈的最小元素值，r记录它的位置

        for(int i=pos;i<=min(pos+rest-,n);i++)

            if(a[i]<minn)

                minn=a[i],r=i;

        while(!st.empty()&&minn>=st.top())    //如果最小元素一直比栈顶元素大，就一直出栈

        {

            printf("%d ",st.top());

            st.pop(),rest++;    //可用栈空间加一

            if(pos+rest-<=n&&a[pos+rest-]<minn)    //栈空间的改变使得我们可以比较下一位置

                minn=a[pos+rest-],r=pos+rest-;

        }

        if(st.empty()||minn<st.top())    //栈为空或最小值小于栈顶元素值，就将最小元素前的元素全部入栈

        {

            for(int i=pos;i<r;i++)

                st.push(a[i]);

            printf("%d ",a[r]);

            rest-=r-pos,pos=r+;    //空间减小，未处理元素位置改变

        }

    }

    while(!st.empty())

    {

        printf("%d ",st.top());

        st.pop();

    }

    printf("\n");

    return ;

}