填坑Ⅰ | 簡單的資料結構

19. 填坑Ⅰ

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

Description

又是北湖深坑，驚不驚喜，意不意外？！

Rack覺得用水填湖太沒意思了，用石頭填坑多有意思，假設北湖的地面還是一維的，每一塊寬度都為1，高度是非負整數，用一個陣列來表示，現提供不限量的1x2規格的石頭，問是否可以將北湖填平，（所有地面到達同一高度即為填平）

注：石頭只能水平或垂直填放，

Input

樣例有多組輸入至檔案末尾；每組用例占兩行；

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

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

Output

若能填平則輸出“YES”，否則輸出“NO”，

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

一、預熱知識

在說具體的演算法之前，首先我們要知道堆疊這個資料結構，之前在 “括號匹配” 里我已經簡單提到過堆疊，關于堆疊，你現在只需要知道兩點

1、它的特點：單口出入，先進后出，

2、它的使用
注意，小學期你直接學會c++封裝的STL的使用即可，至于它是怎么實作的，下學期資料結構這門課有你學的，

#include <stack>  //匯入庫
using namespace std;  //確定命名空間

stack<int>  s;  //定義一個元素是整型的堆疊，命名為s

int a;
s.push(a);   //將整型變數壓入堆疊頂

s.size();   //回傳堆疊內元素個數

s.empty();  //回傳堆疊是否為空

/* 注意，以下的操作必須先保證堆疊不為空，否則會re */

int b = s.top();  //查看堆疊頂元素，存入變數b中

s.pop();  //出堆疊：堆疊頂元素彈出（注意，這個函式回傳值為空）

如果你學有余力，也可以看看雞翅總結的堆疊的資料結構筆記，貼心傳送門：

Stack | 堆疊的陣列實作

Stack | 堆疊實作 —— 后綴運算式

Stack | 堆疊實作 —— 符號配對

二、演算法分析

下面來分析一下這道題：
用1x2的石頭填坑，應該這樣理解：可以每次將單位長度升高2米，或者可以將連續兩個單位長度同時增長1米，

由于我們最后的目的就填平至任意整數高度，那么對于兩個同高的相鄰地方，他們絕對是不會影響我們的結果的，因為我們可以一米一米地對他倆增高，到任意我們想要的高度，故兩兩相同高度的地方我們可以直接忽略！比如高度1 2 2 3，我們可以直接視為1 3相鄰，忽略其中兩個，所以相鄰的定義就放大了，（這里一定要弄明白，這是整個思路的核心，如果不明白就看看后面的再仔細想想）

那么我們的思路就出來了，下面是最清楚的思路，其他方法都可以等價地替換成這個方法的處理，所以以下的方式可以正確地解決判斷問題：

Ⅰ、 首先找到最高點，

Ⅱ、 將石頭以1為底2為高來使用，我們盡量將每一處升高到最高點處：

• 與最高點相差奇數個高度，可以填至與最高處只相差一米，記為1
• 與最高點相差偶數個高度，可以恰好填至與最高處齊平，記為0

Ⅲ、然后依次遍歷記錄下來的整個01串，有相同的在一起可以兩兩相消，如果最后01串內元素大于1，那么說明北湖永遠填不平嘍！

你不能理解的就是為啥可以兩兩相消吧，看看如下例子（測驗用例1：2 1 1 2 5），我們先讓每一列貼近最高點，最后的01串為10010，接著可以消成110，接著可以消成0，所以最后輸出YES

認真理解一下2、3列為什么不影響最后的結果，我們可以直接將2、3列抵消掉？你想想我們怎么再在如下基礎上填平，想好了你估計能明白，因為2、3它們可以以1為單位配合到任何高度，不影響我們的結果，可以直接忽略！！！這里有點只可意會的感覺，你如果想不通就多想幾個用例....

三、演算法實作

你現在應該想到了演算法應該怎么實作吧！先找到最高點，然后依次記錄每一點與最高點相差高度的奇偶性，奇數記為1，偶數記為0，然后討論這個01陣列...然后得出結果....前面的思路都是對的，而如果你用陣列這個資料結構儲存，到最后去處理陣列里存盤的01串結果，就有點繁瑣了...但是！你有沒有想到你沒有用到堆疊誒！有更加簡單處理01串的辦法！用堆疊！

你想想堆疊的特點要怎么應用到這個題里呢！堆疊每次只能訪問和處理堆疊頂的元素，如果我們依次討論并將相同的0/1消掉，是不是堆疊就特別合適呢！這么說好抽象，堆疊這種微妙的作用，你仔細看看例子來理解：

好了，下面給出完整AC代碼：

不對，再另外提幾嘴，別嫌我啰嗦，說不定給你減少幾小時debug的時間，

1、scanf回傳值的問題

不知道你有沒有注意過，樂學提交題目經常會給你回傳這樣一個warning，（雖然我們程式員經常忽略warning只在乎error）

這就是字面意思，你忽略了scanf函式的回傳值！什么？我用了這么久的scanf函式還有回傳值！？我從來沒有用過啊，它不是輸入的嗎！可是你可能忘了c里所有函式都有設定回傳值（void為空），從這里我們可以看到scanf回傳值為int型別，什么意思呢？這個會回傳一個是否成功輸入的標識，具體的我就不說了，當 c 在處理輸入時，一一讀取檔案內容，當每有可以讀取的時候，scanf的回傳值就是EOF， EOF是一個C標準庫定義的常量，不知道你是否還依稀記得 C 語言里把常量用大寫字母來標識，(就比如下面代碼我就定義了一個常量MAXN，只不過是宏定義的形式哈...)

2、回圈輸入必須注意

這道題又是回圈處理輸入的一個題，很多朋友會先寫出一般的處理代碼再套上回圈，或許你也苦惱過為啥我運行過沒有問題呀，再次運行就不對了呢？這種的多樣例測驗一定要注意，如果你沒有在每次回圈前將變數都初始化，你很有可能后面一直在反復在之前的基礎上使用變數！最好的檢測方式就是輸入兩次一樣的用例，看看結果是否相同，如果不同，那么恭喜你中招了！

所以每定義一個變數就對它初始化這是一個很棒的編程習慣，基本資料型別比如int，double之類的我就不說了，陣列我們通常用string.h或cstring類中的memset函式進行初始化，堆疊我們一般在使用前要初始化為空！

這里的易錯點就是，你沒有每次把堆疊清空！！后面的運行就會以上一次堆疊內剩余元素打底，

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

using namespace std;

#define MAXN 200010

long long int a[MAXN] = {0};
stack<int> stk;

int main() {
    long long int n;

    //當輸入沒有中止的時候，讀入 n
    while (EOF != scanf("%lld", &n)) {

        /* 初始化 */
        int maxElement_index = 0;  //記錄對高點的下標
        memset(a, 0, sizeof(a[0]));   //將陣列a全都賦值為 0
        while (!stk.empty())  //清空堆疊
            stk.pop();

        /* 處理輸入 */
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            //找出最高點下標
            if (a[i] > a[maxElement_index])
                maxElement_index = i;
        }

        /* 核心演算法部分 */
        int temp;
        for (int i = 1; i <= n; i++) {
            if ((a[maxElement_index] - a[i]) % 2 == 1) //差的高為奇數
                temp = 0;
            else  //差的高為偶數
                temp = 1;

            if (!stk.empty() && temp == stk.top())  //堆疊非空的前提下：與前一個可以對應相消時
                stk.pop();
            else
                stk.push(temp);
        }

        /* 處理結果 */
        int remainCount = stk.size();   //計算堆疊內剩余元素
        if (remainCount <= 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

End

歡迎關注個人公眾號“雞翅編程”，這里是認真且乖巧的碼農一枚，旨在用心寫好每一篇文章，平常會把筆記匯總成推送更新~