是这几天 学习 紫书遇到的一个问题 之前在学校的时候尝试着做过
题目如下
自己大概知道是这么个意思 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("%sn", ok ? "YES" : "NO"); } return 0; }
123456789101112131415161718192021222324252627之所以之前未理解到是因为自己一直只想到了用两个容器 自然就不懂一个栈和A居然还有个B
自己理解一遍大概是这样target数组中存放的是出去后的火车队 判断进站前按照12345顺序的火车是否可以通过一个站台C（栈）来实现出去的火车队
关键就是这三个判断语句
如果A（当前进站的火车头）等于target【B】(当前应该出站的火车头）那么他们是可以实现的 跳过然后判断下一个进站的火车头和下一个应该出站的火车头
如果不相等 判断下一条语句
如果栈C不为空并且栈顶元素就等于当前应该出站的火车号的话 那么就让它出栈出站 然后判断下一个
如果不满足这个条件 则继续下一个判断
加如A（当前进站车厢的号）小于等于n（车厢数量） 也就是说栈顶的元素不能出站满足条件 当前可以进站的元素也不满足条件 那就只有让它进栈了
否则—如果连进栈的机会都没有了（所以进站的车厢都在栈里或者出站了） 那么前面又没有满足条件出站的车厢 那么就已经不能满足题目条件了 直接break；跳出循环就可以了
栈的几个主要操作是可以 应用 了 只是运用在做题里对我而言还有难度
