louisfghbvc的部落格

題目連結:   https://onlinejudge.org/external/5/514.pdf

題目大意:  用一個 1 ~ n 的 數列， 問能不能排列出 題目給的數列

思路:  目標為a，現有b 用stack暫存c，檢查b的值是否比a大。

3 種狀況 :

a<b表示stack有值，檢查stack上方，

a與b值一樣，則b++，

a>b 表示b太小，則先把數字存入stack直到b = a

代碼:  

#include <bits/stdc++.h>
#define N 1005
using namespace std;

int arr[N];
int main()
{
    int n;
    while(cin >> n, n){
        while(cin >> arr[0], arr[0]){
            for(int i = 1; i < n; ++i) cin >> arr[i];
            stack<int> st;
            int now = 1;
            bool ok = 1;
            for(int i = 0; i < n; ++i){
                if(now == arr[i]) now++;
                else if(now < arr[i]){
                    while(now < arr[i]){
                        st.push(now++);
                    }
                    now++;
                }
                else{
                    if(!st.empty() && st.top() == arr[i]) st.pop();
                    else ok = 0;
                }
            }
            puts(ok ? "Yes" : "No");
        }
        puts("");
    }
}