Skip to content

11049: 【原1049】火车调度

题目

题目描述

author: 苏春智 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1049

Description

有一条东西方向的铁路穿过小城A,小城A有一个火车调度站,示意图如下:

火车调度

现在有N列火车自东向西依次开过来了,按照到达的先后次序编号为0号到N-1号。 根据调度局的要求,小城A的调度站要改变这些列车驶离A城的顺序。 为了达到这一目的, 调度站在任意时刻可以执行以下三种操作之一:

  • 如果调度站还有剩余空间,则可以令下一列开来的火车进入调度站;
  • 如果调度站内有列车,则可以令调度站最前方的火车离开调度站并驶离A城;
  • 可以命令下一列开来的火车不经过调度站而直接驶离A城。

不过小城A的调度站实在太小了,只能容纳M列火车,请帮忙确认调度站能否完成任务。

例子

如果有4列火车开来,调度站可以容纳2列火车,调度局要求火车按照2、1、3、0的顺序驶离A城,则此任务可满足,一种可能的方案如下:

Step 1:火车0进入调度站;

Step 2:火车1进入调度站;

Step 3:火车2不经过调度站驶离A城;

Step 4:火车1从调度站驶离A城;

Step 5:火车3不经过调度站驶离A城;

Step 6:火车0从调度站驶离A城;

当然,你只需要回答是否可行,不需要列出一种可行方案。

Input Format

第一行是一个正整数\(T\),表示本测试数据有多少个独立的测试点。( \(T \leq 300\) )

之后有\(T\)个独立的测试点,每个测试点占两行。 第一行有两个数字\(N\)和\(M\),分别表示开来的火车数量,以及调度站最多可容纳的火车数量,两个数字之间用一个空格隔开。 第二行有\(N\)个整数,他们都在\(0\)到\(N-1\)之间,且不重复,用空格隔开,表示火车驶离A城的次序。

\(N\)是正整数,且\(N \leq 1000\);\(M\)是非负整数,且\(M \leq 1000\)。 \(M\)可能为\(0\)(这也许说明调度站的工作人员罢工了,或者正在这个考场考试)。

Output Format

输出共\(T\)行,每行对应一个测试点。如果能够调度,则回答YES,否则回答NO。 输出请注意大小写,每行行末直接回车,不要有其他字符。

Sample Input

2
4 2
2 1 3 0
5 2
2 4 3 1 0

Sample Output

YES
NO

Hint

对每个测试数据,仅当其内部每个测试点都回答正确才得分。 从概率上讲,如果你采取随机回答YES/NO的方式,你只有大约\(2^{-300}\)的概率骗到分,这大约相当于宇宙中质子数量的倒数。

FineArtz's solution

/* 火车调度 */
#include <iostream>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--){
        int n, m;
        cin >> n >> m;
        int stack[1005], size = 0;
        int a[1005];
        bool flag = true;
        for (int i = 1; i <= n; ++i){
            cin >> a[i];
        }
        int i = 0, j = 1;
        while (i < n){
            if (a[j] > i){
                stack[++size] = i;
                if (size > m){
                    flag = false;
                    break;
                }
                ++i;
            }
            else if (a[j] == i){
                ++i;
                ++j;
            }
            else{
                if (size == 0 || stack[size] != a[j]){
                    flag = false;
                    break;
                }
                --size;
                ++j;
            }
        }
        if (flag){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
}

ligongzzz's solution

#include "iostream"
using namespace std;

class my_stack {
public:
    int stack_data[100000] = { 0 };
    int _size = 0;

    void push(int val) {
        stack_data[_size++] = val;
    }
    void pop() {
        --_size;
    }
    int top() {
        return stack_data[_size - 1];
    }
    bool empty() {
        return _size == 0;
    }
    int size() {
        return _size;
    }
};

int main() {
    int num;
    cin >> num;
    for (; num > 0; num--) {
        int n, m;
        cin >> n >> m;

        int data[2000];
        my_stack trainz;
        for (int i = 0; i < n; i++) {
            cin >> data[i];
            trainz.push(n - i - 1);
        }

        my_stack station;
        bool flag = false;

        //循环判断是否入栈
        for (int i = 0; i < n; i++) {
            if (!station.empty() && station.top() == data[i])
                station.pop();
            else if (!trainz.empty() && trainz.top() == data[i])
                trainz.pop();
            else if (!trainz.empty() && station.size() < m) {
                station.push(trainz.top());
                trainz.pop();
                i--;
            }
            else
                flag = true;
        }

        if (flag)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;

    }

    return 0;
}

LuminousXLB's solution

// 1049. 火车调度
// #554576 正确 / 分数100 / 时间49ms / 内存10536kb
#include <iostream>
#include <stack>

using namespace std;

bool arrange()
{
    int N, M;
    stack<int> park;

    cin >> N >> M;
    cin.get();

    int awayseq[1024];
    for (int i = 0; i < N; ++i) {
        cin >> awayseq[i];
    }

    if (M > N) {
        return true;
    }

    int i = 0;
    for (int next = 0; next < N; next++) {

        if (next == awayseq[i]) {
            i++;
            while ((!park.empty()) && (i < N) && (park.top() == awayseq[i])) {
                i++;
                park.pop();
            }
        } else {
            park.push(next);
            if ((int)park.size() > M) {
                return false;
            }
        }
    }

    return park.empty();
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif

    int T;
    cin >> T;
    cin.get();

    for (int i = 0; i < T; ++i) {
        if (arrange()) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

Neight99's solution

#include <iostream>

using namespace std;

template <class T>
class seqStack {
   private:
    T* data;
    int nowSize;
    int maxSize;
    // void doublespace();
   public:
    seqStack(int initSize = 10);
    seqStack(const seqStack<T>&);
    ~seqStack();
    int size() const;
    void push(T);
    T top();
    T pop();
    bool isEmpty();
    seqStack<T>& operator=(const seqStack<T>&);
    T& operator[](int);
};

template <class T>
seqStack<T>::seqStack(int initSize) {
    data = new T[initSize];
    nowSize = 0;
    maxSize = initSize;
}

template <class T>
seqStack<T>::seqStack(const seqStack<T>& right) {
    nowSize = right.nowSize;
    maxSize = right.maxSize;
    data = new T[maxSize];
    for (int i = 0; i < nowSize; i++) {
        data[i] = right.data[i];
    }
}

template <class T>
seqStack<T>::~seqStack() {
    delete[] data;
    data = NULL;
}

template <class T>
int seqStack<T>::size() const {
    return nowSize;
}

template <class T>
void seqStack<T>::push(T x) {
    if (nowSize == maxSize) {
        // doublespace();
        return;
    }
    data[nowSize++] = x;
}

template <class T>
T seqStack<T>::top() {
    if (nowSize != 0) {
        return data[nowSize - 1];
    } else {
        return -1;
    }
}

template <class T>
T seqStack<T>::pop() {
    if (nowSize != 0) {
        return data[--nowSize];
    } else {
        return -1;
    }
}

template <class T>
bool seqStack<T>::isEmpty() {
    return (nowSize == 0);
}

template <class T>
seqStack<T>& seqStack<T>::operator=(const seqStack<T>& right) {
    if (this != &right) {
        delete[] data;

        nowSize = right.nowSize;
        maxSize = right.maxSize;
        data = new T[maxSize];
        for (int i = 0; i < nowSize; i++) {
            data[i] = right.data[i];
        }
    }

    return *this;
}

template <class T>
T& seqStack<T>::operator[](int x) {
    return data[nowSize - x - 1];
}

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int N, M, h = 0, *out, temp;
        bool key = 1;
        cin >> N >> M;

        seqStack<int> Station(M + 1);
        out = new int[N];

        for (int i = 0; i < N; i++) {
            cin >> out[i];
        }

        /*for(int i=0;i<N;i++){
            bool go=0;
            while(i==out[h]||Station.top()==out[h]){
                if(i==out[h] && go==0){
                    h++;
                    go=1;
                }
                if(Station.top()==out[h]){
                    temp=Station.pop();
                    h++;
                }
            }
            if(Station.size()==M){
                cout<<"NO"<<'\n';
                key=0;
                break;
            } else if (Station.size()<M && go==0){
                Station.push(i);
            }
        }*/
        for (int i = 0; i < N; i++) {
            if (Station.size() == M + 1) {
                key = 0;
                break;
            }
            Station.push(i);
            while (Station.top() == out[h]) {
                Station.pop();
                h++;
            }
        }

        if (Station.size() != 0) {
            key = 0;
        }

        if (key == 1) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }

        delete[] out;
    }

    return 0;
}

q4x3's solution

/**
 * 栈模拟
 **/
#include <iostream>

using namespace std;
int tmp, nex, flag = 1;

struct sstack
{
    int a[1233];
    int top;
};


int main() {
    int T;
    cin >> T;
    for(int i = 0;i < T;++ i) {
        int N, M;
        nex = 0; flag = 1;
        cin >> N >> M;
        sstack s;
        s.top = 0; s.a[0] = nex;
        for(int i = 0;i < N;++ i) {
            cin >> tmp;
            while(flag) {
                if(s.a[s.top] == tmp) {
                    -- s.top;
                    break;
                }
                ++ s.top;
                ++ nex;
                if(nex + 1 > N) flag = 0;
                s.a[s.top] = nex;
                if(s.top > M) flag = 0;
            }
        }
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

skyzh's solution

#include <iostream>
using namespace std;

template <typename T>
class Stack {
public:
    T *data;
    int ptr;
    Stack(int cap) : data(new T[cap]), ptr(0) {}
    ~Stack() { delete[] data; }
    void push(const T& d) { data[ptr++] = d; }
    T pop() { return data[--ptr]; }
    T top() { return data[ptr - 1]; }
    bool empty() { return ptr == 0; }
    void print() { for (int i = 0; i < ptr; i++) cout << data[i]; printf("\n"); }
    void clear() { ptr = 0; }
};

int main() {
    int T;
    scanf("%d", &T);
    Stack <int> s(2000);
    int n, m;
    int c;
    for (int i = 0; i < T; i++) {
        s.clear();
        scanf("%d%d", &n, &m);
        bool found = true;
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            scanf("%d", &c);
            if (found) {
                if (cnt <= c) {
                    while (cnt < c) s.push(cnt++);
                    cnt++;
                    if (s.ptr > m) found = false;
                } else {
                    if (s.empty()) found = false;
                    else if (s.top() != c) found = false;
                    else s.pop();
                }
            }
        }
        if (found) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

victrid's solution

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

template <typename T>
class basestack {
private:
    T container[1000] = {0};
    T* top_ptr;
    int total;
    bool balance_changed;

public:
    basestack() {
        top_ptr = container;
        total   = 0;
    }
    int height() { return total; }
    T push(T p) {
        *top_ptr = p;
        top_ptr++;
        total++;
        return *(top_ptr - 1);
    }
    T top() { return total ? *(top_ptr - 1) : -1; }
    T pop() {
        if (total == 0)
            return *top_ptr;
        top_ptr--;
        total--;
        return *(top_ptr - 1);
    }
    void clear() {
        top_ptr = container;
        total   = 0;
    }
};
bool ans[300];
int proc[1001];
basestack<int> stk;
int T, N, M, now, nums;
int main() {
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        stk.clear();
        now    = 0;
        nums   = 0;
        ans[i] = true;
        for (int j = 0; j < N; j++)
            scanf("%d", &proc[j]);
        while (nums != N) {
            if (proc[nums] == now) {
                nums++;
                now++;
                continue;
            }
            if (proc[nums] == stk.top()) {
                nums++;
                stk.pop();
                continue;
            }
            stk.push(now++);
            if (stk.height() == M + 1) {
                ans[i] = false;
                break;
            }
        }
    }
    for (int i = 0; i < T; i++)
        printf(ans[i] ? "YES\n" : "NO\n");
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int t,st[2000],top,n,m,p,x,s;
bool flag;
int main() {
    scanf("%d",&t);
    for (int i=0;i<t;++i){
        scanf("%d%d",&n,&m);
        s=0;
        flag=true;
        top=-1;
        for (int j=0;j<n;++j)
        {
            scanf("%d",&x);
            while (s<n&&s!=x&&((top>=0&&st[top]!=x)||top==-1))
            {
                if (top>=m-1) flag=false;
                st[++top]=s++;
            }
            if (s==x) s++;
            if (top>=0&&st[top]==x) top--;
        }
        if (top==-1&&s==n&&flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

yyong119's solution

#include<cstdio>
#include<stack>
using namespace std;
int M, N;
const int SIZE = 1010;
int order[SIZE];

int main() {

    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);

        for (int i = 0; i < N; ++i) scanf("%d", &order[i]);

        stack<int> ControlStation;
        int i = 0, j = 0;
        bool ok = true;
        while (j < N) {
            if (i == order[j]) {
                i++; j++;
            }
            else
            if (!ControlStation.empty() && ControlStation.top() == order[j]) {
                ControlStation.pop(); j++;
            }
            else
            if (i < N && ControlStation.size() < M)
                ControlStation.push(i++);
            else {
                ok = false; break;
            }
        }
        printf("%s\n", ok ? "YES" : "NO");
    }
    return 0;
}