本次作业不需提交报告。

题目描述

Input

共两行。

第一行为两个整数n,m。

第二行为以空格分隔的n个整数,保证为{1, 2, …, n}的一个排列,表示待判断可行性的驶出序列{a1,a2,…,an}。

Output

若驶出序列可行,则输出操作序列,其中push表示车厢从A进入S,pop表示车厢从S进入B,每个操作占一行。

若不可行,则输出No。

Sample Input 1 

5 2
1 2 3 5 4
Sample Output 1

push
pop
push
pop
push
pop
push
push
pop
pop

代码

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

int main(){
    int n, m;
    int B[10000];   //B队列
    bool step[20005];   //记录操作 0压入 1弹出
    bool flag = false;  //标记是否出现错误
    cin >> n >> m;
    stack<int> s;   //代表中转端
    
    for(int i = 0; i < n; i++){
        cin >> B[i];
    }

    int i = 1, j = 0, k = 0;  //当前数字i 操作步骤标记j B队列索引k
    while(i <= n){
        if(s.empty()){
            s.push(i++);
            step[j++] = 0;
        }
        else{
            if(s.top() == B[k]){
                s.pop();
                step[j++] = 1;
                k++;
            }
            else{
                s.push(i++);
                step[j++] = 0;
                if(s.size() > m){
                    flag = 1;
                    break;
                }
            }
        }
    }

    //剩余元素的弹出讨论
    while(!s.empty()){
        if(s.top() != B[k]){
            flag = 1;
            break;
        }
        else{
            s.pop();
            step[j++] = 1;
            k++;
        }
    }

    if(flag)
        cout << "no";
    else{
        for(int l = 0; l < j; l++){
            if(step[l])
                cout << "pop";
            else
                cout << "push";
            cout << endl;
        }
    }
    
    return 0;
}

测试
测试