首页 > 代码库 > POJ1363 Rails 验证出栈序列问题（转）

POJ1363 Rails 验证出栈序列问题（转）

2024-07-17 08:09:17   229人阅读

题目地址： http://poj.org/problem?id=1363

此题只需验证是否为合法的出栈序列。

有两个思路：
1、每个已出栈之后的数且小于此数的数都必须按降序排列。复杂度O(n^2)，适合人脑。

 

//思路 1 不对！！！  

例如 数据 ，               3 5 2 4 1              --------                正确答案为 no

2、另一个思路就是直接模拟入栈出栈过程。虽然模拟毫无技巧可言，但复杂度O(n)，优于算法1。适合电脑。

代码如下：

 

[java] view plaincopy
  1. for; i < N; i++){  
  2. ifwhileelseifnullnewelse;  
  3. break
----------------------------------------------------------
代码 按思路 1 做的，错误。。测试数据 ，3 5 2 4 1  正确答案应该是 no

//wrong      poj 1363//accepted   zoj 1259//accepted   uva 514#include<iostream>#include<cstring>#include <algorithm>using namespace std;const int maxn=1000+10;int main(){	int a[maxn];	int b[maxn];	int n;	while(cin>>n && n!=0)	{		while(1)		{			memset(a,0,sizeof(a));			memset(b,0,sizeof(b));			int i,j;			int x;			cin>>a[1];			if(a[1]==0)				break;			for(i=2;i<=n;i++)				cin>>a[i];			int max;			int t=true;			for(i=1;i<=n;i++)			{				if(b[i]!=1)				{					b[i]=1;					max=a[i];					for(j=i+1;j<=n;j++)					{						if(a[j]<max&&b[j]!=1)						{							if(a[j]!=max-1)							{								t=false;								break;							}							else							{								max--;								b[j]=1;							}						}					}				}				if(t==false)					break;			}			if(t==false)				cout<<"No"<<endl;			else				cout<<"Yes"<<endl;		}		cout<<endl;	}	return 0;}

---------------------------------------
课本 正确代码 ，较复杂。
 
#include<iostream>#include<cstring>using namespace std;const int maxn=1000+10;int main(){	int n,p[maxn];	cin>>n;	while(n)	{		int x,max=0;		cin>>x;		while(x)		{			memset(p,0,sizeof(p));			bool valid=true;			for(int i=1;i<=n;i++)			{				if(valid)				{					bool ok=true;					for(int i=x+1;i<=max;i++)						if(p[i]==1)						{							ok=false;							break;						}					if(!ok)						valid=false;					else					{						max=(max>x?max:x);						p[x]=2;						for(int i=x-1;i>0 && !p[i];i--)							p[i]=1;					}				}				if(i<n)					cin>>x;			}			cout<<(valid ? "Yes" : "No")<<endl;			cin>>x;		}		cout<<endl;		cin>>n;	}	return 0;}

------------------------------------------------------------
 
 
 
 


联系
我们