铁轨问题

题目描述

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

输入描述

第一行，一个整数n,表示有n节车厢；接下来一行有n个整数，表示对应顺序

输出描述

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

样例

输入

5
3 5 4 2 1

输出

Possible

题目分析

本题实质上就是对出栈的一个模拟，如果不使用STL去做，可以用数组模拟一个栈，定义一个变量top作为栈顶。

思路

以3 5 4 2 1这个出栈序列为例

1. 一开始栈为空
2. 由于 3 不在栈中，就需要把 1,2,3 依次进栈， 再出栈， 这样符合出栈序列第 一个数是
   3，当前栈为{1,2} 。
3. 第 2 个出栈的是 5，5 不在栈中，则就把 4,5 压栈，再出栈就可以得到 5，此时栈为{1,2,4}
4. 第 3 个出栈的是 4，正好是栈顶元素，直接出栈，此时栈为{1,2}
5. 第 4 个出栈的是 2，正好是栈顶元素，直接出栈，此时栈为{1}
6. 第 5 个出栈的是 1，正好是栈顶元素，直接出栈，此时栈为{}
   在模拟的过程中没有碰到要出栈的数在栈中但不是栈顶元素的情况，所以该方案可行。

代码

#include 
#include 
#include 
using namespace std;
int n;
int a[1005];
int stk[1005],top=0;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int cnt=1;for(int i=1;i<=n;i++){while(cnt<=a[i])stk[top++]=cnt++;if(stk[top-1]=a[i]){top--;} else{printf("Impossible\n");return 0;}}cout<<"Possible"<<endl;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！