一、题意
一列火车车厢号从1...n,问能否依靠一个中转站将车厢顺便变为指定的排序。
有若干组数据,每组数据第一行一个n,之后若干行每行为一询问。
二、解析
显然用栈模拟中转站。
车厢从1...n首先必然进栈,然后根据执行排序来判断是否需要出栈。
三、代码
#include <iostream> #include <stack> using namespace std; const int maxn = 1000 + 5; int n, a[maxn]; int main() { while(cin >> n && n) { while(cin >> a[0] && a[0]) { for(int j = 1; j < n; j ++) cin >> a[j]; stack<int> stk; int j = 0; for(int i = 1; i <= n; i ++) { stk.push(i); while(!stk.empty() && stk.top() == a[j]) stk.pop(), j ++; } cout << (stk.empty() ? "Yes\n" : "No\n"); } cout << endl; } }
四、归纳
- 注意栈的题目执行stk.top()前一定要判定!stk.empty()
- 注意栈的题经常性是将出栈操作放在while循环中,思考时要特别注意不要遗漏这一细节。