Description
给你一个正整数 $n$ ，然后给你 $n$ 个正整数 $a_1$ ~ $a_n$ ，问你是否有可能存在入栈顺序为 $1,2,3,…,n$ ，出栈顺序为 $a_1$ ~ $a_n$ 的情况，共有 $T$ 组数据。
$1 \leq n \leq 1000,1 \leq T \leq 10$ 。
Solution
考虑使用 模拟 和 栈 来解题。
直接模拟进栈和出栈，当当前进栈的数的编号为当前要出栈的数的编号时就出栈。这个过程可以用两个指针搞，一个在栈上，一个在指定顺序上，一旦当前两个指针指的位置相同时就要用一个 $\text{while循环}$ 来出 栈 。 注意 ，有可能一次将多个数出栈，如果最后栈上还有数就不行，否则可以。
时间复杂度 $O(n)$ ，具体细节见 代码 部分。
然后这道题目就做完了。
Code
1 | #include<cstdio>
|
2 | #include<cstring>
|
3 | using namespace std;
|
4 | int n,a[1001],wei,f[1001],tou;
|
5 | inline int read()
|
6 | {
|
7 | int s=0,f=1;
|
8 | char c=getchar();
|
9 | while (!(c>='0')&&(c<='9')) {
|
10 | if (c=='-') f=-1;
|
11 | c=getchar();
|
12 | }
|
13 | while ((c>='0')&&(c<='9')) {
|
14 | s=s*10+c-'0';
|
15 | c=getchar();
|
16 | }
|
17 | return s*f;
|
18 | }
|
19 | int main()
|
20 | {
|
21 | while(1)
|
22 | {
|
23 | n=read();
|
24 | if(!n)break;
|
25 | while(1)
|
26 | {
|
27 | a[1]=read();
|
28 | if(!a[1])break;
|
29 | for(int i=2;i<=n;i++)a[i]=read();
|
30 | tou=0;wei=1;
|
31 | for(int i=1;i<=n;i++)
|
32 | {
|
33 | f[++tou]=i;
|
34 | if(a[wei]==f[tou])
|
35 | {
|
36 | while(a[wei]==f[tou]&&tou>0)
|
37 | {
|
38 | wei++;tou--;
|
39 | }
|
40 | }
|
41 | }
|
42 | if(tou)
|
43 | {
|
44 | printf("No\n");
|
45 | }
|
46 | else
|
47 | {
|
48 | printf("Yes\n");
|
49 | }
|
50 | }
|
51 | puts("");
|
52 | }
|
53 | return 0;
|
54 | }
|
