填坑Ⅱ | 簡單的資料結構

20. 填坑Ⅱ

成績	10	開啟時間	2020年09月17日 星期四 12:00
折扣	0.8	折扣時間	2020年09月24日 星期四 12:00
允許遲交	否	關閉時間	2020年10月10日 星期六 23:00

Description

emmm，還是北湖深坑，不用驚喜，不用意外。

我們繼續用石頭填！北湖的地面依舊是一維的，每一塊寬度都為1，高度是非負整數，用一個陣列來表示。

還是提供不限量的1x2規格的石頭。但是這一次是 Dark來填坑，他有很強烈的強迫症，所有的石頭只能水平擺放（寬為2，高為1）。問這樣是否可以將北湖填平。（所有地面到達同一高度即為填平）

Input

樣例有多組輸入至檔案末尾；

每組用例佔兩行；

第一行輸入1個整數 n表示北湖地面總寬度；

第二行輸入 n個整數,用空格間隔，表示地面高度。

Output

若能填平則輸出「YES」，否則輸出「NO」。

	測試輸入	期待的輸出	時間限制	記憶體限制	額外程序
測試用例 1	5↵ 2 1 1 2 5↵ 3↵ 4 5 3↵ 3↵ 1 2 3↵	YES↵ NO↵ NO↵	1秒	64M	0

---

        emmmm我總覺得個填坑Ⅱ和Ⅰ反了，但是怎麼今年依舊還是這個順序....相信看懂Ⅰ的朋友這個Ⅱ真的小菜一碟！ 

        第一題的傳送門，請看懂第一題再來看第二題：填坑Ⅱ | 簡單的資料結構

 

既然不可以以1為底2為高去填，那麼與第一題的思路差別就是：

1. 最後的結果判定為yes的條件：棧最後為空 或 棧內剩餘的唯一元素必須是最高點（好好想想這是為啥）
2. 我們不可以對坑進行預處理（將他們儘可能填到最高處），我們直接討論之後的情況。情況變得非常簡單：入棧的不是01，而是它們本身的高度！

       依次討論每一個初始高度，如果相鄰的同高且兩側都比它們倆低，那麼可以消去忽略不計。如果最後序列裡有超過一個元素或剩餘的唯一元素不是最高點，則輸出NO！如果在討論的過程中，棧頂元素比棧內高，那我們可以不必繼續討論....

---

你們可以多畫一些測試用例來理解如上思路，雞翅能力有限(兩點了，該睡會了)說不太明白，上面都是精華，剩下的就交給大家了~

附上完整ac程式碼：

 

#include<cstdio>
#include<cstring>
#include<stack>

using namespace std;

long long int a[200010] = {0};
stack<int> stk;   //定義一個棧

int main() {
    long long int n, x = 2e18;

    //當存在輸入的時候
    while (scanf("%lld", &n) != EOF) {
        memset(a, 0, sizeof(a[0]));   //將陣列初始化為0
        while (!stk.empty())  //清空棧
            stk.pop();

        long long maxHeight = 0;
        for (long long i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            //記下最高值
            if (a[i] > maxHeight)
                maxHeight = a[i];
        }

        for (long long height : a) {
            if (!stk.empty() && height == stk.top())  //棧非空且可以對應時
                stk.pop();
            else {   //不可以消去
                if (!stk.empty() && stk.top() < height)   //如果比前一個高
                    break;
                else  
                    stk.push(height);
            }
        }

        long long remainCount = stk.size();
        if (!remainCount)
            printf("YES\n");
        else if (remainCount == 1 && stk.top() == maxHeight)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

---

End

歡迎關注個人公眾號「雞翅程式設計」，這裡是認真且乖巧的碼農一枚，旨在用心寫好每一篇文章，平常會把筆記彙總成推播更新~