3.2 station

★实验任务

一天，silchen 突然对列车的进出站问题产生了兴趣，如下图所示：

有 n 辆列车，按 1~n 编号，只能从 A 进站，或从 B 出站。

现在 silchen 知道列车进站序列是多少，进站序列为 1~n 的某个排列，于是 silchen 想知道列车出站序列中字典序最大的序列是多少，即要使第一个出站列车编号尽量大，在保证第一个最大情况下使第二个出站列车编号尽量大，依次类推

如图，列车从 A 进站，进站顺序为 1, 2, 3, 4, 5

列车从 B 出站，出站顺序为 5, 4, 3, 2, 1

★数据输入

第一行一个正整数 n（1<=n<=100000）。

第二行包含 n 个正整数，为 1~n 的某个排列对于 20%的数据：1<=n<=10

对于 50%的数据：1<=n<=1000

对于 100%的数据：1<=n<=100000

★数据输出

一行输出字典序最大的出站顺序，数字间用一个空格隔开，行末没有空格

★样例

大体思路：

想法蛮简单的，只要我们知道当前列车的编号（假设为编号为B，现在处于栈顶，刚进station），如果我们发现后面还有个C列车编号大于B，显然为了保证字典序最大，我们必须让C先于B出站，一直这样重复直到所有车出站。所以n应该第一个出站。

输入时我们用一个数组存下输入序列，为了得到B之后的最大列车编号，我们建立后缀数组。

#include <cstdio>
#include <stack>
using namespace std;
int main()
{
	int n,l,r=1000000;
	int a[100005];
	int post[100005];//后缀数组，post[i] :位置i之后列车中编号最大值 
	stack <int> s;
	scanf ("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf ("%d",&a[i]);
		if (a[i]==n)//n之前的列车统统进栈 
			r=i;
		if (i<=r)
			s.push(a[i]);
	}
	post[n]=a[n];
	for (int i=n-1;i>=1;i--)
	{
		if (a[i]>post[i+1])
			post[i]=a[i];
		else
			post[i]=post[i+1]; 
	}
	printf ("%d",n);
	s.pop();r++;
	while (r<=n)
	{
		while (( r<=n  && post[r] > s.top() ) || (s.empty()) )//栈外存在比栈顶编号大的列车，进栈，直到栈外没有比栈顶大的。（栈为空进栈一个，在进行比较） 
		{
			s.push(a[r]);
			r++;
		}
		while ( !s.empty() && r<=n && s.top() > post[r] )//栈顶元素比栈外的都大，出栈。 
		{
			printf (" %d",s.top());
			s.pop();
		}
	}
	while (!s.empty() )
	{
		printf (" %d",s.top());
		s.pop();
	}
	return 0;
} 

更新一下去年的车站问题。。。

3.2 station

★实验任务

一天，小 L 突然对列车的进出站问题产生了兴趣，如下图所示：

列车只能从A 进站，或从B 出站。列车从A 进站，进站顺序为 1, 2, 3, 4, 5列车从 B 出站，出站顺序为 5, 4, 3, 2, 1

现在，小 L 想知道：列车从A 进站，进站顺序为 1~n

列车从 B 出站，给定出站的顺序，判断是否可能按照这个顺序出站

★数据输入

第一行一个正整数 n（1<=n<=1000）。

第二行包含 n 个正整数，为 1~n 的某个排列

★数据输出

若能够按照给定的顺序出站，输出”YES”（没有引号） 否则，输出”NO”（没有引号）

★样例 

大体思路是围绕着给定序列进行的进出栈操作。

如果给定序列的数字在栈顶，弹出栈，看序列的下一个数是否在栈顶，若不在，查看是否在还未入栈，若未入栈，把该数字之前的数都入栈；不在栈顶也不在栈外，则无法形成该序列；

车站问题的排序个数是卡特兰数 

#include <cstdio>
#include <stack>
using namespace std;
int a[1005];
int b[1005];
int main()
{
	int n;
	stack <int> s;
	scanf ("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf ("%d",&a[i]);
		b[i]=i;
	}
	int r=1;
	while (r!=a[1])
	{
		s.push(r);
		r++;
	}
	r++;
	int l=2;
	while(l<=n&&r<=n)
	{
		if (s.empty() || s.top()!=a[l] )
		{
			while (r<=n&&(s.empty() || s.top()!=a[l]))
			{
				s.push(b[r]);
				r++;
			}
			if (s.top()!=a[l])
			{
				printf ("NOn");
				return 0;
			}
			else
				s.pop();
		}
		else if (s.top()==a[l]&&!s.empty())
			s.pop();
		l++;
	}
	printf ("YESn");
	return 0;
}