Pop Sequence
题目
题目地址：地址
思路
例如题目例子中可能的序列：3 2 1 7 5 6 4 可以用一种反证法，假设这个序列是存在的，我们现在模拟这个序列生成的过程，如果生成的过程与题目条件一致，则序列存在，否则，则不存在； 首先我想要3！一看堆栈里面啥都没有，只能往里面放，第一次只能放1，发现1不等于3，那就再往里面放2，还不等于，那就放3，哎，等于啦！把3拿出来，再看我们假设成立的序列，该2了，我们以看栈顶是2，是2，把2拿出来，同理，把1拿出来，这时候我们需要7了，站里面没东西了，继续往里面加，加4，不行，加5，不行，加6，不行，加7，哎可以啦，把7拿出来，然后下一个需要的是6，发现栈顶是7，不一样，继续往栈里面放，发现没东西放了，而我们现在只能拿7，达不到我们假设序列的要求，所以我们假设的序列是失败的！
综上分析：我们相当于是对假设序列的每个元素逐一分析，同时模拟入栈过程，判断每个元素是否能被堆栈返回有一个不能返回，则失败。
代码
#include"stdio.h"
#include"malloc.h"
struct Stack
{
int Data
[1000];
int Max
, Now
;
};
int main() {
Stack s
;
int p_num
, c_num
, i
, j
;
scanf("%d %d %d", &s
.Max
, &p_num
, &c_num
);
int* t
;
t
= (int*)malloc(c_num
* sizeof(int));
for (i
= 0; i
< c_num
; i
++) {
int k
= 0;
s
.Now
= -1;
int* List2
;
int* List1
;
List2
= (int*)malloc(p_num
* sizeof(int));
List1
= (int*)malloc(p_num
* sizeof(int));
int h
;
for (h
= 0; h
< p_num
; h
++) {
List1
[h
] = h
+ 1;
scanf("%d", &List2
[h
]);
}
for (j
= 0; j
< p_num
; j
++) {
if (s
.Now
== -1) {
s
.Now
++;
s
.Data
[s
.Now
] = List1
[k
];
k
++;
}
while (s
.Data
[s
.Now
] != List2
[j
] && s
.Now
< s
.Max
- 1) {
if (k
< p_num
)
{
s
.Now
++;
s
.Data
[s
.Now
] = List1
[k
];
k
++;
}
else
{
break;
}
}
if (s
.Data
[s
.Now
] == List2
[j
]) {
s
.Now
--;
}
else
{
break;
}
}
if (j
== p_num
) {
t
[i
] = 1;
}
else
{
t
[i
] = 0;
}
}
int f
;
for (f
= 0; f
< c_num
; f
++) {
if (t
[f
] == 1) {
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
