Content

在一個叫「堆疊市」的城市中有一個有名的火車站。由於地形限制以及經費的關係，火車站及唯一的鐵路的樣子如下圖：

現在火車從A方向來，預定從B方向離開。火車共有N節車廂（N <=1000），並且各車廂依次以1到N來編號。你可以假設各車廂在進站之前可以單獨與其他車廂分離，也可以單獨離開車站到往B方向的鐵軌上。你也 可以假設在任何時間火車站都可以容納所有的車廂。但是一旦一節車廂進站後，就不能再回到A方向的鐵軌上了，並且一旦離開車站往B方向後，也不能再回到車 站。

現在你的任務是寫一個程式，判斷火車能否以一特定的排列方式在B方向的鐵軌上。

Input

輸入含有多組測試資料。每組測試資料的第一列，有1個整數N，其意義如上所述。對於此組測試資料接下來有0到多個不等的測試，每個測試一列，每列有N個整數，內容為1,2,......,N的任意排列。當遇到僅含有一個0的一列，代表該組測試資料結束。

N=0代表輸入結束，請參考Sample Input。

Output

對每一組測試資料的每個測試，輸出該1,2,......,N的任意排列是否可能。如果可能，請輸出yes，若不可能則輸出No。

每組測試資料後亦請空一列。請參考Sample Output。

Sample Input #1
5
1 2 3 4 5
5 4 3 2 1
5 4 1 2 3
0
7
4 5 3 7 6 2 1
0
0
Sample Output #1
Yes
Yes
No

Yes

C++

#include <iostream>
#include <stack>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
    int n;
    while( cin >> n )
	{
		if( n == 0 )  break;
        while(true)
		{
			int i;
			int temp=1;
			int arr[n];
            stack <int>stk;
            
            cin>>arr[0];
            if(arr[0]==0){
            	break;
			}
			for(i=1;i<n;i++){
				cin>>arr[i];
			}

			//輸入完成
			for(i=0;i<n;i++) {
				if(!stk.empty() && stk.top()==arr[i]){
					stk.pop();
				}
				else if(arr[i]>=temp){
					for(int j=temp;j<arr[i];j++){
						stk.push(j);
						
					}
					temp=arr[i]+1;
				}
				else break;
			}

            if( i == n )  cout << "Yes" << endl;
			else  cout << "No" << endl;
        }
        cout << '\n';
    }
    return 0;
}

python

while True:
    try:
        n=int(input())
        if n==0:break
        while True:
            arr=list(map(int, input().split()))
            if len(arr)==1 and arr[0]==0:break
            
            stack=[0]
            original=[i for i in range(1,n+1)]
            flag=True

            
            for i in arr:
                while True:
                    if i == stack[-1]:
                        stack.pop()
                        break
                    elif i>stack[-1]:
                        stack.append(original.pop(0))
                    elif i<stack[-1]:
                        flag=False
                        break
                if flag==False:
                    print("No")
                    break
            else:print("Yes")
    except:break

 

文章標籤
全站熱搜
創作者介紹
創作者 趴趴熊日常 的頭像
趴趴熊日常

資工趴趴熊的小天地

趴趴熊日常 發表在 痞客邦 留言(1) 人氣(260)