stack的运用
紫书上给的代码是wa的 但思路没问题 是在输入上有bug
然而我也每太看懂这个题对0那块的处理要求
连着的两个0是什么啊
懒得搞了
贴一个过了的代码和书上的代码
#include <iostream> #include <stack> using namespace std; const int len = 1024; int coaches[len]; int main() { int n; while (cin >> n, n) { stack<int> s; // read the required permutaion while ( cin >> coaches[0], coaches[0]) { for (int i = 1; i < n; i++) { cin >> coaches[i]; } int lenB = 0, aId = 1; bool ok = true; while (lenB < n) { if (aId == coaches[lenB]) { aId++; lenB++; } else if(!s.empty() && s.top() ==coaches[lenB]) { s.pop(); lenB++; } else if(aId <= n) s.push(aId++); else { ok = false; break; } } cout << (ok ? "Yes" : "No") << endl; } cout << endl; } return 0; }书上的
#include<iostream> #include<stdio.h> #include<stack> //WA using namespace std; const int MAXN = 1000 + 10; int n, target[MAXN]; int main() { while(scanf("%d", &n) == 1) //输入 一共n辆火车 { if(n!=0) { stack<int> s; //声明栈S int A = 1, B = 1; // A:进站顺序 1,2,3,...,n B:出站顺序（数组target的下标） 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) //要进站的与出站的不同，只进站，先等着，当栈顶与目标相同时再出（上一个if） { s.push(A++); } else { ok = 0; //正常结束循环为b=n, 若前几种情况都不符合，则不能按照要求顺序出站，break break; } } printf("%s\n", ok ? "Yes" : "No"); } else printf("\n"); } return 0; }
