问题 A: 火车站(stack)
时间限制: 1 Sec 内存限制: 128 MB
提交: 251 解决: 137
[提交][状态][讨论版]
题目描述
火车站只有一条铁路，所有的火车都停在那里。所以所有的火车都是从一边进站，从另一边出站。如果A列先进入铁路，然后B列在A列离开之前进入铁路，那么A列在B列离开之前不能离开。下图说明了问题所在。车站里最多有9列火车，所有的火车都有一个ID（编号从1到N），火车按照O1的顺序进入火车，火车是否可以按照O2的顺序驶出。
输入
输入包含几个测试用例。
每个测试用例由一个整数（列车数）和两个字符串组成。两个字符串分别为列车入站顺序和列车出站顺序。
输出
如果不能按照指定顺序出站，输出“No”。
如果可以，输出“Yes”，然后输出出入站顺序（对于进入铁路的列车，应输出“in”，对于出铁路的列车，应输出“out”）。在每个测试用例之后打印一行包含“FINISH”。
样例输入
3
3 123 321
3 abc cab
3 123 123
样例输出
Yes
in
in
in
out
out
out
FINISH
No
FINISH
Yes
in
out
in
out
in
out
FINISH
#include <iostream>
#include "stack"
#include "vector"
using namespace std;int main() {int t;cin >> t;while (t--) {int len;vector<string> show; //记录s的每一次进栈和出栈string s1, s2;cin >> len >> s1 >> s2;stack<char> s;int p1 = 0, p2 = 0; //定义两个游标用来比较while (p2 != len) {while (p1 < len && s1[p1] != s2[p2]) { //还没入完s.push(s1[p1++]);show.push_back("in");}if (p1 == len) break;if (s1[p1] == s2[p2]) { //入栈一次，出栈一次p1++; p2++;show.push_back("in");show.push_back("out");}//当p1==len时，用s的栈顶去和s2[p2]比较while (!s.empty() && s.top() == s2[p2]) {show.push_back("out");s.pop();p2++;}}if (s.empty() && p2 == len) {cout << "Yes" << endl;for (int i = 0; i < show.size(); i++) {cout << show[i] << endl;}}else {cout << "No" << endl;}cout << "FINISH" << endl;}return 0;
}
