題目說明#
有一個農場有寬度為 \(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;
}
