POJ 1363 Railsはスタックシーケンスが正当かどうかを判断する
5336 ワード
テーマリンク:http://poj.org/problem?id=1363(lrj白書練習問題)
一つの出桟シーケンスが1,2,3,…,nから桟処理を経て生成できるかどうかを判断する.
考え方:
I:定理:スタックシーケンスが不正である<=>kが存在し、iこの定理で判断するとO(n^3)の時間がかかり,不適切である.
II:シミュレーションでいい:スタックをシミュレートして、1現在スタックに入る要素が次のスタック要素であれば、直接スタックに入れてスタックを出させて、次のスタックにジャンプします.
②現在のスタックトップ要素が次のスタック要素である場合は、スタックを出させます.
③そうでなければ現在の要素をスタックに入れて次の要素を見る
スタックに入るすべての要素が処理されると、スタック内の要素が順次ポップアップされ、スタック要素と一致しない要素がある場合は、スタックシーケンスが合法ではありません.
一つの出桟シーケンスが1,2,3,…,nから桟処理を経て生成できるかどうかを判断する.
考え方:
I:定理:スタックシーケンスが不正である<=>kが存在し、i
II:シミュレーションでいい:スタックをシミュレートして、1現在スタックに入る要素が次のスタック要素であれば、直接スタックに入れてスタックを出させて、次のスタックにジャンプします.
②現在のスタックトップ要素が次のスタック要素である場合は、スタックを出させます.
③そうでなければ現在の要素をスタックに入れて次の要素を見る
スタックに入るすべての要素が処理されると、スタック内の要素が順次ポップアップされ、スタック要素と一致しない要素がある場合は、スタックシーケンスが合法ではありません.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int s[1010];
int main(){
//freopen("data.txt","r+",stdin);
int n;
while(cin>>n){
if (n == 0) break;
while(cin>>s[0]){
stack <int> t;
//memset(s,0,sizeof(s));
if (s[0] == 0){
break;
}
for (int i = 1; i < n; i ++){
cin>>s[i];
}
int b = 0;
int i = 0;
while (i < n){
if (i + 1 == s[b]){
b ++;
i ++;
}
else if (!t.empty() && t.top() == s[b]){
t.pop();
b ++;
}
else{
t.push(i + 1);
i ++;
}
}
int ok = 1;
while(!t.empty() && b < n){
if (t.top() != s[b]){
ok = 0;
break;
}
t.pop();
b ++;
}
if (ok) cout<<"Yes
";
else cout<<"No
";
}
cout<<endl;
}
return 0;
}