UVA 514 Rails

UVA 514 Rails

題目概述:

給一個數列，問是否可能為一個順序1到n陸續丟進stack，pop順序自訂使得剛好為該數列。

思路:

就直接模擬stack，然後看是否會矛盾。

AC code:

//By SCJ

//uva 514

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int n;

   bool fir=0;

   while(cin>>n,n!=0)

   {

       while(1)

       {

           bool fg=0;

           int t,cnt=2;

           stack<int> s;

           s.push(1);

           bool ok=1;

           for(int i=0;i<n;++i)

           {

               cin>>t;

               if(t==0){fg=1;break;}

               while(cnt<=n&&(s.empty()||s.top()!=t))

               {

                   s.push(cnt++);

               }

               if(s.empty()||s.top()!=t) {ok=0;}

               else s.pop();

           }

           if(fg) break;

           if(ok) cout<<"Yes\n";

           else cout<<"No\n";

       }

       cout<<endl;

   }

}