数据结构作业三列车调度

wanakiki 收录于数据结构

2019-04-21 约 377 字预计阅读 1 分钟

本次作业不需提交报告。

题目描述

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;
}

目录

数据结构作业三 列车调度

题目描述

代码

数据结构作业三列车调度