洛谷-UVA514 铁轨 Rails

我会带着你远行 2023-05-29 06:43 17阅读 0赞

## 题目描述 ##

[PDF][]

![format_png][]

## 输入格式 ##

![format_png 1][]

## 输出格式 ##

![format_png 2][]

## 题意翻译 ##

某城市有一个火车站，铁轨铺设如图。有n节车厢从A方向驶入车站，按进站的顺序编号为1～n。你的任务是判断是否能让他们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如，出栈顺序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。 为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每节车厢，一旦从A移入C，就不能返回A了;一旦从C移入B，就不能返回C了。也就是说，在任意时刻，只有两种选择：A到C和C到B。

对于每一组数据，第一行是一个整数 N。接下来若干行数据，每行 N 个数，代表 1 ~ N 车厢的出栈顺序，最后一组数据只有一个整数 0 。对于每一组数据，在最后输出空行。

最后一组数据的 N=0 ，不输出。

n<=1000

## 输入输出样例 ##

**输入 \#1**复制

5
    1 2 3 4 5
    5 4 1 2 3
    0
    6
    6 5 4 3 2 1
    0
    0

**输出 \#1**复制

Yes
    No
    Yes

标准答案：

#include<bits/stdc++.h>
    using namespace std;
    const int maxsize=1000+5;
    int n,B[maxsize];
    int main()
    {
        while(cin>>n&&n)
        {
            while(1)
    		{
    			int i=1,j=1;
    			cin>>B[1];
    			if(!B[1])
    				break;
    	        for(int i=2;i<=n;i++)
    	        	cin>>B[i];
    	        stack<int>s;
    	        while(i<=n)
    	        {
    	            if(i==B[j])
    	            {
    	                i++;
    	                j++;
    	            }
    	            else
    	                s.push(i++);
    	            while(!s.empty()&&s.top()==B[j])
    				{
    					j++;
    					s.pop();
    				}
    			}
    			if(j<=n)
    				cout<<"No"<<endl;
    	        else
    				cout<<"Yes"<<endl;
    		}
    		cout<<endl;
        }
        return 0;
    }

**自己的答案：**

#include <bits/stdc++.h>
    using namespace std;
    
    int main(){
    	int n;
    	int A[1000];
    	int B[1005];
    	while(cin>>n&&n!=0){
    		while(true){
    			cin>>B[0];
    			if(B[0]==0){
    				break;
    			}
    			//B出栈序号 
    			for(int i=1;i<n;i++){
    				cin>>B[i];
    			}
    
    			//A依次进站 
    			for(int i=0;i<n;i++){
    				A[i]=i+1;
    			}
    		
    			//模拟A出栈、B进栈(也就是出栈顺序)
    			int b=0; //B栈初始下标 
    			stack<int> stack; //C中转栈	
    				
    			for(int i=0;i<n;i++){
    				//A出栈(可能入C，可能入B)
    				if(A[i]!=B[b]){
    					stack.push(A[i]);
    				}else{
    					b++;				
    				}
    				//判断是否可从C出栈到B 
    				while(!stack.empty()&&stack.top()==B[b]){
    					stack.pop();
    					b++;
    				}					
    			}
    			
    			//判断C栈是否为空
    			if(stack.empty()){
    				cout<<"Yes"<<endl;
    			} else{
    				cout<<"No"<<endl;
    			}				
    		}	
    		cout<<endl;//不加这里测试用例不通过		
    	}	
    	return 0;
    }

[PDF]: https://uva.onlinejudge.org/external/5/p514.pdf
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTUxNC9hOGYwYWY5YTJhZGVhZWFhYjFkMTkwNmMzZjMxMTZhZmEwYzZiNDQ0LnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTUxNC8wM2I0ZTE5MjRlNzQ5NDhiYzAxZjNmNDJjZDVhMzE1MDJmMWMzOWI2LnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTUxNC83ZTk2NzgwYTg3NmY4MjcxODBkZWEyNTEzOWMxYzc3YmJmYjk0OTM3LnBuZw?x-oss-process=image/format,png