本次作业不需提交报告。
题目描述
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;
}