stack-铁轨问题

每辆火车都从A方向驶入车站，再从B方向驶出车站，同时它的车厢可以进行某种形式的重新组合。假设从A方向驶来的火车有n节车厢(n<1000)，分别按顺序编号为1，2，...,n。假定在进入车站之前每节车厢之间都是不连着的，并且它们可以自行移动，直到处在B方向的铁轨上。另外假定车站C里可以停放任意多节的车厢。但是一旦当一节车厢进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨后，它就不能再回到车站C。负责车厢调度的工作人员需要知道能否使它以a1，a2，...，an的顺序从B方向驶出。请写一个程序，用来判断能否得到指定的车厢顺序。

【输入格式】

输入由两行组成：

第一行有n(n<1000),表示有n节车厢。

第二行n个数表示一组需判定的车厢。

【输出格式】

对于每个输入输出有一行,每行根据判断,如果能正常驶出输出"YES",否则输出"NO"。

【输入输出样例】

5 4 3 2 1

Yes

5 4 1 2 3

6 5 4 3 2 1

Yes

 #include<cstdio>

 #include<stack>

 using namespace std;

 const int maxn =  + ;

 int n, target[maxn];

  int main()

  {

      while(scanf("%d", &n)==)

      {

          stack<int> s;

          int A = , B = ;

          for(int i = ; i <= n; i++)

          scanf("%d", &target[i]);

          int ok = ;

          while(B <= n)          //B表示出栈的车的数量

          {

              if(A==target[B])    //A表示出栈数量加上入栈车辆和

              {

                  A++; B++;

              }

              else if(!s.empty()&&s.top()==target[B])

              {

                  s.pop(); B++;

              }

              else if(A<=n) s.push(A++);

              else

              {

                  ok = ; break;

              }

          }

         printf("%s\n", ok ? "Yes" : "No");

      }

      return ;

  }

巴特西

stack-铁轨问题

最新文章

热门文章