首页 > 代码库 > 铁轨问题

铁轨问题

2024-09-11 01:41:28   216人阅读

题目描述

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

输入

第一行输入t(1<=t<=10)，表示测试数据的组数。
第一行一个整数n，表示有n节车厢。
接下来一行有n个整数，表示对应顺序。

输出

输出仅一行。若可以，则输出“Possible”，否则输出“Impossible”。
 

样例输入

1
5
3 5 4 2 1

样例输出

Possible

数据范围限制

1<=n<=1000
在中转站C中，车厢符合后进先出的原则，因此是一个栈。代码如下：
#include<cstdio>#include<stack>using namespace std;const int MAXN=1000+10;int m,n,target[MAXN];int main() {    scanf("%d",&m);    for(int k=1; k<=m; k++) {        scanf("%d",&n);            stack<int> s;            int A=1,B=1;            for(int i=1; i<=n; i++)                scanf("%d",&target[i]);            int ok=1;            while(B<=n) {                if(A==target[B]) {                    A++;                    B++;                } else if(!s.empty()&&s.top()==target[B]) {                    s.pop();                    B++;                } else if(A<=n)s.push(A++);                else {                    ok=0;                    break;                }            }            printf("%s\n",ok?"Possible":"Impossible");            }    return 0;}

 

铁轨问题


联系
我们