当前位置:编程学习 > C/C++ >>

zoj - 1259 - Rails

——>>暑假曾在汝佳神牛的白书上见过这题,原来在zoj上也有……顺序序列与目标序列匹配,匹配上就转到一节车厢;不能的话再用栈顶与目标序列匹配;也不能的话看顺序序列能否放入栈中,能就继续,不能就“No”。只可惜……“Yes”被我写成了“YES”, ”No"被我写成了“NO”,WA了3次!!!每块后都加空行被我弄成了块间加空行,又"PE"了一次......AC之路不容易的呀……
[cpp]
#include <iostream> 
#include <stack> 
 
using namespace std; 
 
const int maxn = 1000 + 10; 
 
int main() 

    int N, i; 
    int target[maxn];       //用来存目标序列 
    while(cin>>N) 
    { 
        if(N == 0) return 0; 
 
        while(cin>>target[1]) 
        { 
            if(target[1] == 0) break;       //一组测试结束 
 
            for(i = 2; i <= N; i++) 
                cin>>target[i]; 
 
            stack<int> st; 
            int init = 1, cur = 1, ok = 1;      //init为初始序列,即1,2,3...,cur为目标序列的下标,ok为能否转换的标记 
            while(cur <= N)     //一直到匹配完所有的车厢 
            { 
                if(init == target[cur])     //当驶来的车厢号与目标序列车厢号匹配时 
                { 
                    init++;     //转到匹配下一节车厢 
                    cur++;      //转到匹配下一节车厢 
                } 
                else if(!st.empty() && st.top() == target[cur])     //当栈中的车厢号与目标序列车厢号匹配时 
                { 
                    st.pop();       //退栈,转到匹配下一节车厢 
                    cur++;          //转到匹配下一节车厢 
                } 
                else if(init <= N)      //如果不相匹配但还没到始入的最后一辆车厢时 
                { 
                    st.push(init++);        //驶入车厢进栈,且转到下一节车厢 
                } 
                else        //如果不相匹配且已到始入的最后一辆车厢时 
                { 
                    ok = 0; 
                    break; 
                } 
            } 
            if(ok) cout<<"Yes"<<endl; 
            else cout<<"No"<<endl; 
        } 
        cout<<endl; 
    } 
    return 0; 

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,