Pop Sequence 题解
2024-10-09 07:02:59
Pop Sequence(PAT)
https://www.nowcoder.com/pat/5/problem/4090
前言:
PAT上一道Stack的应用题,简化版的有《信息学一本通·普及篇》的车厢调度
题目简述:
输入依次给定三个不大于1000的整数:m,n,k
其中m是栈的最大长度,有n个元素,进行k种出栈猜测
以下k行,输入出栈猜测,针对每种猜测,判断是否可行,可行则输出“YES”,反之输出“NO”
思路:
将每次给定的出栈猜测当做数组a,然后将元素从1-n依次进行入栈再进行solve处理。
处理规则:
(1)、设数组当前下标为now。从a[1]-a[now]判断a[i]是否等于栈顶元素,如果有,则弹出当前元素,并将a[i]标记为用过;如果不等于,则跳出循环不考虑后面的a[i](联系栈的特征“后进先出”——上面出去下面才能出去,便于理解)
(2)、如果当前栈的size超过了m,则说明栈满了,直接打标记最后输出“NO”
(3)、所有solve处理完后,判断当前栈是否为空,如果为空则说明第i种出栈猜测(1<=i<=k)正确,输出“YES”;如果不为空则说明不正确,输出“NO”
因为感觉自己没有讲得很清楚,现在给出草图帮助大家理解(如果还不是很清楚,可以结合代码哦qwq)
代码Code:
#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[1001],b[1001];
stack<int> num;
inline int solve(int now,int last) {
int lasts=last; //相当于标记哪些i用过
for(register int i=last;i<=now;i++) {
if(num.empty()) break; //如果为空直接跳出
if(num.top()==a[i]) { //相等就弹出栈,并标记当前i用过
lasts++;
num.pop();
}
else break; //因为是栈,所以不相等就跳出
}
return lasts;
}
int main() {
scanf("%d%d%d",&m,&n,&k);
for(register int i=1;i<=k;i++) {
int start=1;
bool p=true; //标记是否size>m
for(register int j=1;j<=n;j++) {
scanf("%d",&a[j]); //输入一个就处理一个
num.push(j);
if(num.size()>m) p=false;
else start=solve(j,start);
}
//cout<<num.size()<<" ";
if(!num.empty()||p==false) puts("NO");
else puts("YES");
while(!num.empty()) num.pop(); //因为是多种操作,所以记得清空
}
return 0;
}
再讲一下简化版的车厢调度吧,因为只有一种猜测,所以程序只需要主程序更改一点就可以A掉,主程序如下:
int main() {
scanf("%d",&n);
int start=1;
bool p=true;
for(register int j=1;j<=n;j++) {
scanf("%d",&a[j]);
num.push(j);
start=solve(j,start);
}
if(!num.empty()||p==false) puts("NO");
else puts("YES");
return 0;
}
最新文章
- Eclipse不自动编译java文件的终极解决方案
- 3大主流NoSQL数据库性能对比测试报告
- JavaScript_变量的自动转换和语句
- 计算方法(一)用C#实现数值迭代
- C++ 中dynamic_cast&;lt;&;gt;的用法
- SQL Server--导入和导出向导
- Mysql ibd文件恢复指南
- Spring Boot 2.0(三):Spring Boot 开源软件都有哪些?
- CountDownLatch 使用说明
- Cocos2D粒子发射器的纹理
- #SQL1242错误
- [UE4]C 语言动态数组
- Django REST Framework应用
- session的本质及如何实现共享?
- 可变参数模拟printf()函数实现一个my_print()函数以及调用可变参数需注意的陷阱
- vuex的一个坑
- 拒绝了对对象 &#39;sp_OACreate&#39; (数据库 &#39;mssqlsystemresource&#39;,架构 &#39;sys&#39;)的 EXECUTE 权限。
- git --fast-version-control
- Python基础-week06 面向对象编程进阶
- iptables之centos6版本常用设置