蒜头君的魔法机
蒜头君有一台神奇的魔法机，它能将输入的序列进行一系列复杂的变换，输出原序列的另一种排列方式。蒜头君十分好奇魔法机的工作原理，终于有一天他尝试着把魔法机拆开研究了。
通过一系列复杂的演算，蒜头君终于发现了魔法机的工作原理：其实魔法机就是一个栈，根据栈先进后出的性质，每次一个数字进栈或将栈顶元素弹出，由此可以产生不同的出栈序列，出栈序列就是原序列的另一种排列了。
在研究完原理后，蒜头君凭借记忆很快就把魔法机组装好了。现在蒜头君想测试下魔法机在组装完成后是否出现问题。
首先他将 1 到 N 这 N 个数字依次输入魔法机里，然后随机写下一组序列a，现在他想知道能否通过魔法机得到序列a，聪明的你能帮蒜头君算一算吗？
输入格式
输入有两行，第一行是一个正整数 N(1≤N≤100)，表示输入魔法机序列的长度，第二行是序列a，共有 N 个整数，表示要得到的目标序列。
序列为 1 到 N 的排列，即序列a长度为 N，保证序列中的整数都不相同，且整数在区间 [1, N] 内。
输出格式
输出一行，如果能通过魔法机得到序列a，则输出YES，否则输出NO。
实现代码
思路：模拟魔法机的实现，其中a数组是期望的出栈顺序；栈r是存的是n到1的数据，栈顶在1的位置，按从大到小排；栈s是魔法机本体；遍历a数组，如果s栈的栈顶元素和a[i]不一样（还不到出栈的时候），就把r栈的栈顶元素给s栈（试试下一个元素是否可以按照期望出栈），如果遇到s栈的栈顶元素大于a[i]的情况，表示这个期望的出栈顺序无法实现。
可能表述不到位，以下是实现代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct
{
int data[101];
int top;
}sqstack,*sqslink;
int push(sqslink &s,int x)
{
if(s->top >=100) return 0;
else
{
s->top++;
s->data[s->top]=x;
return 1;
}
}
bool emptystack(sqslink s)
{
if(s->top <0) return 1;
else return 0;
}
int pop(sqslink &s)
{
if(emptystack(s)) return 0;
else
{
s->top--;
return(s->data[s->top]);
}
}
int main()
{
int n;
cin>>n;
int a[101];
for(int i=0;i<n;++i)
cin>>a[i];
sqslink s,r;
s=(sqslink)malloc(sizeof(sqstack));
s->top=0;
r=(sqslink)malloc(sizeof(sqstack));;
r->top=0;
for(int i=n;i>=1;--i)
push(r,i);
int i=0;
s->data[s->top]=0;
while(1)
{
if(i==n) break;
if(s->data[s->top]==a[i])
{
pop(s);
i++;
continue;
}
else if(s->data[s->top]>a[i])
{
cout<<"NO";
return 0;
}
push(s,r->data[r->top]);
r->top-=1;
}
cout<<"YES";
return 0;
}
|
收藏Shaw的博客谢谢喵~
