题解 P1750 【出栈序列】

· · 题解

k表示在数组中的位置，pos表示当前扫描数组的最小值的位置，count表示当前输出的个数 首先先看栈还需要几个元素，如果栈还需要n个元素，就把数组指针k开始的n个元素，找出其中的最小值，并把最小值的元素记录为pos，然后把pos位置及之前的位置压入栈中。 如果栈空，就压栈。如果栈顶元素小于k的位置的元素，就弹栈

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<cmath>
using namespace std;

/*
6 3
5 2 3 8 7 4

2 3 5 4 7 8
*/
int main()
{
    int n,c;
    cin>>n>>c;
    int a[10005];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    stack <int> s;
    int k = 0;
    int count = 0;
    int pos  =0;
    while(count+s.size()<n){
        int min = 2e9;
        //找出数组的前（c-s.size()）元素中的最小值，pos记录最小值的位置
        for(int i=k;i<k+c-s.size()&&i<n;i++){
            if(a[i]<min){
               min = a[i];
               pos = i;
            }
        }
        //当栈为空的时候或者栈顶元素大于最小元素，就将找到的最小元素（包括）以及他之前的元素压入占中
        if(s.empty()||min<=s.top()){
            for(int i=k;i<=pos;i++){
                s.push(a[i]);
            }
            k = pos+1;//pos是最小元素，压入栈中，k表示还未处理的数组元素的最先开始的位置，pos位置的元素在栈中，pos+1还未处理
        }
        cout<<s.top()<<" ";
        s.pop();
        count++;//记录输出数量
    }
    //将栈中的元素输出
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}