2016-07-08

OI / Data Structure

26 minutes read (About 3867 words)

「SuperOJ 142」车厢调度

车厢调度

题目描述

有一个火车站，铁路如图所示，每辆火车从 A 驶入，再从 B 方向驶出，同时它的车厢可以重新组合。假设从 A 方向驶来的火车有 n 节（n<=1000），分别按照顺序编号为 1，2，3， \cdots ，n 。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到 B 处的铁轨上。另外假定车站 C 可以停放任意多节车厢。但是一旦进入车站 C，它就不能再回到 A 方向的铁轨上了，并且一旦当它进入 B 方向的铁轨，它就不能再回到车站 C。

负责车厢调度的工作人员需要知道能否使它以 a1,a2, \cdots ,an 的顺序从 B 方向驶出，请来判断能否得到指定的车厢顺序。

输入格式

输入文件的第一行为一个整数 n ，其中 n<=1000，表示有 n 节车厢，第二行为 n 个数字，表示指定从 B 方向驶出的车厢顺序。

输出格式

如果可以得到指定的车厢顺序，则输出一个字符串“YES”，否则输出“NO”（注意要大写，不包含引号）。

样例数据 1

输入

1 2	5 5 4 3 2 1

输出

YES

样例数据 2

输入

1 2	5 3 1 2 4 5

输出

NO

分析

栈的运用,注意要在for循环内判断。

源码

#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
stack<int> st;
inline bool test(int* arr, int len) {
    int pos = 0;
    for (int i = 1; i <= len; i++) {
        st.push(i);
        while (!st.empty()) {
            if (st.top() != arr[pos])
                break;
            else {
                st.pop();
                pos++;
            }
        }
    }
    return st.empty();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int* arr = new int[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    if (test(arr, n))
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

# Data Structure, String

Comments

xehoth

明日は明日の风が吹く

Shanghai / Chengdu, China

Posts

336

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now