当前位置: 首页 >> 基本常识
PAT Advanced 1051 Pop Sequence
  
  来源: www.scpt.net.cn 点击:1473

1051弹出序列

给定一个最多可保存M个数字的堆栈。按1,2,3,…,N的顺序随机弹出N个数字。你应该知道给定的数字序列是否是堆栈中可能的弹出序列。例如,如果M是5,N是7、我们可以从堆栈中获得1,2,3,4,5,6,7,但不能获得3,2,1,7,5,6,4 .

输入规范:

每个输入文件包含一个测试用例。对于每种情况,第一行包含3个数字(都不超过1000)、 M(堆栈的最大容量)、N(推送序列的长度)和k(要检查的弹出序列的数量).接下来是K行,每一行都包含一个由N个数字组成的流行序列。一行中的所有数字都用空格隔开

输出规格:

对于每个弹出序列,如果它确实是堆栈中可能的弹出序列,请在一行中打印"是“,否则打印"否" .

样本输入:

样本输出:

解题思路

大意:

给定一个容量为m的栈,从栈底到顶的依次推为1- n,给定k次枚举,判断是否能按照输入的要求通过依次爸爸,输出得到刚刚输入的值,如果能输出,否则,并且堆中最大容量为m .如果超过m的话,也算

思路过程:

每次都将1-n的数推进堆中,之后栈顶和输入的[idx]比较,如果相同的话,idx指向a中的下一个位置,堆栈要流行音乐出栈顶元素,一直检测此条件,相同并且栈不为空就一直爸爸,不满足条件时就继续用力。最终堆中存在元素或者中间的过程堆存储的元素个数超过m .输出不,否者为是的。此过程枚举k次即可

解题代码

c模拟堆很简洁,c编译改一下头文件,看了很多其他人写的c版本貌似没看到 比我这18行精简的了吧:

使用补充劳工以下内容:

友情链接:
南坑村信息网 版权所有© www.scpt.net.cn 技术支持:南坑村信息网 | 网站地图