3 123 321 3 123 312
Yes. in in in out out out FINISH No. FINISHFor the first Sample Input, we let train 1 get in, then train 2 and train 3. So now train 3 is at the top of the railway, so train 3 can leave first, then train 2 and train 1. In the second Sample input, we should let train 3 leave first, so we have to let train 1 get in, then train 2 and train 3. Now we can let train 3 leave. But after that we can‘t let train 1 leave before train 2, because train 2 is at the top of the railway at the moment. So we output "No.".HintHint
题意:给出初始序列和序列a和b,和一个栈c ,a只能进c,不能回来,c只能进b,求能否达到目标并打印路径。
典型的栈,直接模拟。
#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #include <ctype.h> using namespace std; typedef long long LL; const int MAX=0x3f3f3f3f; int n ,op[4004]; char a[2005], b[2005], c[2005]; int main() { while(~scanf("%d %s %s",&n,a,b)) { int i=0,j=0,top=-1,k=0; while(j<n) { // b里还有车没匹配 if( a[i] == b[j] ) { //a的第一辆与b直接匹配 op[k++] = 1; op[k++] = 0; i++,j++; } else if( top >= 0 && c[top] == b[j]) { // 栈里的车与b匹配 op[k++] = 0; j++,top--; } else if(i<n) { // 都不匹配就把a里的车入栈 top++; c[top] = a[i]; op[k++] = 1; i++; } else break; //a里没车了直接退出循环 } if(j >= n) { printf("Yes.\n"); for(int i=0;i<k;i++) if(op[i] == 1) printf("in\n"); else printf("out\n"); } else printf("No.\n"); printf("FINISH\n"); } return 0; }
HDU 1022 Train Problem I (数据结构 —— 栈),布布扣,bubuko.com
HDU 1022 Train Problem I (数据结构 —— 栈)
原文:http://blog.csdn.net/u013923947/article/details/38334357