修補圍籬

題目說明

有一個農場有寬度為 $n$ 的圍籬，每個圍籬都有各自的高度，有些圍籬被吹斷了（高度為 $0$ 表示被吹斷了），農場主人要來修補這些圍籬，但他忘記這些壞掉的圍籬原本高度是多少，為了減少成本，他會取斷掉的圍籬位置相鄰左邊和右邊較小的那個高度填上去，求需要多少成本。題目保證不會有兩個相鄰的吹斷圍籬，而穿斷的圍籬有可能位在邊界。

解題思路

讀完題目之後，我們可以先整理出這個策略：

我們需要先宣告一個陣列來儲存圍籬的高度
接著掃過整個陣列
- 如果發現圍籬高度為 $0$ ，則取左右兩邊較小的高度加入答案
最後輸出答案

解題過程

首先在 main 函式中宣告一個大小為 $105$ 的陣列 h 來儲存圍籬的高度：

int h[105];

然後，進入 main 函式，我們需要先宣告一個變數 $n$ 來儲存有幾個圍籬並且輸入變數 $n$ ，初始化一個 $ans$ 變數來儲存我們的答案：

int n = 0, ans = 0;
cin >> n;

依序輸入 $n$ 個圍籬的高度，這裡要使用到 for 迴圈來幫助我們：

for (int i = 1; i <= n; i++) {
    cin >> h[i];
}

接著，我們要掃過整個陣列，當發現高度為 $0$ 就取左右邊比較小的加入答案（這邊我們使用前面章節提到的數學函式來把程式寫的更精簡）：

for (int i = 1; i <= n; i++) {
    // 如果找到被吹斷的圍籬
    if (h[i] == 0) {
        // 取左右兩邊較小的高度加入答案
        ans += min(h[i - 1], h[i + 1]);
    }
}

如果有仔細思考的話，這邊應該會注意到上面的程式碼其實會出一點小問題，原因是當我們掃到邊界的時候，我們對左右兩邊取小的那個一定會取到 $0$ （原因是我們沒有把值輸入進去，且 main 外的陣列預設值為 $0$ ），這樣會造成我們沒算到邊界的情況。

有一個比較巧妙的方法是把第 $0$ 個和第 $n + 1$ 個圍籬的高度先設為一個更大的數，這樣就可以避免這個問題：

// 這邊用 101 是因為題目保證圍籬高度不會超過 100
h[0] = 101;
h[n + 1] = 101;

// 掃過整個陣列並且計算答案
for (int i = 1; i <= n; i++) {
    if (h[i] == 0) {
        ans += min(h[i - 1], h[i + 1]);
    }
}

最後再將答案輸出即可：

cout << ans;

完整程式碼如下：

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

int h[105];

int main(){
    int n = 0,ans = 0;
    cin >> n;
    h[0] = 101;
    h[n + 1] = 101;
    for (int i = 1; i <= n; i++){
        cin >> h[i];
    }
    // 掃過整個陣列並且計算答案
    for (int i = 1; i <= n; i++) {
        // 如果找到被吹斷的圍籬
        if (h[i] == 0){
            // 取左右兩邊較小的高度加入答案
            ans += min(h[i - 1], h[i + 1]);
        }
    }
    cout << ans;
}