1049.火车调度

Description

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

untitled.png

现在有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≤300）之后有T个独立的测试点，每个测试点占两行。 第一行有两个数字N和M，分别表示开来的火车数量，以及调度站最多可容纳的火车数量，两个数字之间用一个空格隔开。 第二行有N个整数，他们都在0到N−1之间，且不重复，用空格隔开，表示火车驶离A城的次序。N是正整数，且
N≤1000；M是非负整数，且M≤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

代码

#include<iostream>
#include<stack>
using namespace std;
#define Maxn 1002

void Judge(int *sequence, int m, int n)
{
        int  index=0; // 火车出站序列索引；
        int  train= 0; // 火车进站序列；
        stack<int> seq;
        while(index<n)
        {
                //判断进站序列是否与出站一样，一样，则直接通过
                if(train == sequence[index])
                {
                    train ++;
                    index++;
                }
                //判断出站火车是否与站内的最前方火车序号一样，一样，则出站

                else if(!seq.empty()&& seq.top() == sequence[index])
                {
                    seq.pop(); //出站
                    index++;
                }

                // 调度火车进站
                else {
                    seq.push(train++);
                    if(seq.size() > m)
                    {
                        cout<<"NO"<<endl;
                        break;
                    }
                }
        }
        if(index == n)
        cout<<"YES"<<endl;
}

int main(){
    int T,N,M;
    cin>>T;
    while(T--)
    {
        cin>>N>>M;
        int sequence[Maxn];
        for(int i=0;i<N;i++)
        {
            cin>>sequence[i];
        }
        Judge(sequence,M,N);
    }
}