是这几天学习紫书遇到的一个问题 之前在学校的时候尝试着做过
题目如下
自己大概知道是这么个意思 C就相当于一个栈 进去的车厢只能倒着出来 后进去的就先出来
代码里不精 还是照着书上的打了一遍 花了一个下午理解了
#include<cstdio>
#include<stack>
using namespace std;
const int MAXN = 1000 + 10;int n, target[MAXN];int main()
{while (scanf("%d", &n) == 1){stack<int>s;int A = 1, B = 1;for (int i = 1; i <= n; i++)scanf("%d", &target[i]);int ok = 1;while (B <= n){if (A == target[B]) { A++; B++; }else if (!s.empty() && s.top() == target[B]) { s.pop(); B++; }else if (A <= n)s.push(A++);else { ok = 0; break; }}printf("%s\n", ok ? "YES" : "NO");}return 0;
}之所以之前未理解到是因为自己一直只想到了用两个容器 自然就不懂一个栈和A居然还有个B
自己理解一遍大概是这样target数组中存放的是出去后的火车队 判断进站前按照12345顺序的火车是否可以通过一个站台C（栈）来实现出去的火车队
关键就是这三个判断语句
如果A（当前进站的火车头）等于target【B】(当前应该出站的火车头）那么他们是可以实现的 跳过然后判断下一个进站的火车头和下一个应该出站的火车头
如果不相等 判断下一条语句
如果栈C不为空并且栈顶元素就等于当前应该出站的火车号的话 那么就让它出栈出站 然后判断下一个
如果不满足这个条件 则继续下一个判断
加如A（当前进站车厢的号）小于等于n（车厢数量） 也就是说栈顶的元素不能出站满足条件 当前可以进站的元素也不满足条件 那就只有让它进栈了
否则—如果连进栈的机会都没有了（所以进站的车厢都在栈里或者出站了） 那么前面又没有满足条件出站的车厢 那么就已经不能满足题目条件了 直接break；跳出循环就可以了
栈的几个主要操作是可以应用了 只是运用在做题里对我而言还有难度
