GMOJ P3035 【铁轨】

Description

给你一个正整数 $n$ ，然后给你 $n$ 个正整数 a 1 a_1 a1​ ~ a n a_n an​ ，问你是否有可能存在入栈顺序为 $1,2,3,...,n$ ，出栈顺序为 a 1 a_1 a1​ ~ a n a_n an​ 的情况，共有 $T$ 组数据。

$1\le n\le 1000,1\le T\le 10$ 。

Solution

考虑使用 模拟 和 栈 来解题。

直接模拟进栈和出栈，当当前进栈的数的编号为当前要出栈的数的编号时就出栈。这个过程可以用两个指针搞，一个在栈上，一个在指定顺序上，一旦当前两个指针指的位置相同时就要用一个 $\text{while循环}$ 来出 栈 。 注意 ，有可能一次将多个数出栈，如果最后栈上还有数就不行，否则可以。

时间复杂度 $O(n)$ ，具体细节见 代码 部分。

然后这道题目就做完了。

Code

#include
#include
using namespace std;
int n,a[1001],wei,f[1001],tou;
inline int read()
{int s=0,f=1;char c=getchar();while (!(c>='0')&&(c<='9')) {if (c=='-') f=-1;c=getchar();}while ((c>='0')&&(c<='9')) {s=s*10+c-'0';c=getchar();}return s*f;
}
int main()
{while(1){n=read();if(!n)break; while(1){a[1]=read();if(!a[1])break;for(int i=2;i<=n;i++)a[i]=read();tou=0;wei=1;for(int i=1;i<=n;i++){f[++tou]=i;if(a[wei]==f[tou]){while(a[wei]==f[tou]&&tou>0){wei++;tou--;}}}if(tou){printf("No\n");}else{printf("Yes\n");}}puts("");}return 0;
}

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