#120. 「6-2」B、车站铁轨
时间限制：1000 ms
内存限制：128 MiB
输入文件：B.in
输出文件：B.out
题目类型：传统
评测方式：文本比较
上传者： liuser
题目描述
有 节车厢从 A 方向驶入车站，按进站顺序编号为 。
你的任务是让他们按照某中特定的顺序进入 B 方向的铁轨并驶出车站。为了重组车厢，你可以借助中转站 C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入 C 的车厢必须按照相反的顺序驶出 C。对于每个车厢，一旦从 A 移入 C，就不能再回到 A 了；一旦从 C 移入 B，就不能回到 C 了。换句话说，在任意时刻，只有两种选择：A->C 和 C->B。
4.png
现在需要你写一个程序，判断给定的 B 方向驶出车站的车箱顺序是否可行，若不可行输出 'no'；若可行则输出 'yes'，并输出要能得到这个出站顺序，中转站 C 至少需要几个存放车厢的位置。
输入格式
输入文件 B.in
第 行一个整数 ，表示有 节车厢；
第 行 个整数，是 的排列，表示 B 方向驶出的车厢顺序。
输出格式
输出文件 B.out
若 B 方向出站车厢顺序不可行输出 "no"，若可行，则输出 "yes"，并在第二行输出中转站至少要提供车厢位置数。
样例
输入样例
5
1 2 3 4 5
输出样例
yes
1
此题因为是A进B出且C底部封闭，所以此题可以用栈的思想：
#include <iostream>
#include <fstream>
using namespace std;
int Stack[100];
int top,bottom;
void initStack()
{
top = bottom = 0;
return ;
}
void push(int n)
{
Stack[top++] = n;
return ;
}
int pop()
{
int n = Stack[--top];
return n;
}
int getTop()
{
int n = Stack[top-1];
return n;
}
bool isEmpty()
{
if(top == bottom)
{
return true;
}
return false;
}
int findit(int x,int n,int a[])
{
for(int i = 0;i < n;i++)
{
if(a[i] == x)
{
return i;
}
}
}
int main()
{
initStack();
int a[100],b[100];
int n;
cout << "输入车厢数：";
//写入文件
/*
ifstream Cin("in.txt");
cin >> n;
cout << "车厢数：" << n << "个" << endl;
Cin.close();
*/
cin >> n;
for(int i = 1;i <= n;i++)
{
a[i] = i;
}
for(int i = 0;i < n;i++)
{
cin >> b[i];
}
bool flag = true;
int m = 0;
for(int i = 0;i < n;i++)
{
int x = b[i];
if(isEmpty())
{
int lo = findit(x,n,a);
for(int j = m;j <= lo;j++)
{
push(a[j]);
}
m = lo+1;
pop();
}
else if(getTop() == x)
{
pop();
}
else
{
int lo = findit(x,n,a);
if(lo < m)
{
flag = false;
break;
}
for(int j = m;j <= lo;j++)
{
push(a[j]);
}
m = lo+1;
pop();
}
}
if(flag)
{
//文件输入
/*
ifstream Cout("out.txt")
cout << "Yes" << endl;
Cout.close();
*/
cout << "yes" << endl;
}
else
{
//文件输入
/*
ifstream Cout("out.txt")
cout << "Yes" << endl;
Cout.close();
*/
cout << "no" << endl;
}
return 0;
}
不知道题目中的输入和输出格式是打印还是写入文件，所以答者把两种方法都写上了，题者可以自行选择