# APCS實作題2021年11月第1題：修補圍籬

> 日期：2023年9月17日
> 作者：王一哲
> 題目來源：110年11月實作題第1題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=g595)

<br />

## 題目

### 問題描述

有一個農場有寬度為 $n$ 的圍籬, 每個圍籬都有各自的高度 $h[1], h[2], \dots, h[n]$。

有些圍籬被吹斷了，農場主人要來修補這些圍籬，但他忘記這些壞掉的圍籬原本高度是多少，為了減少成本，他會取斷掉的圍籬位置相鄰左邊和右邊較小的那個高度填上去，問需要多少成本。

題目保證不會有兩個相鄰的吹斷圍籬，而穿斷的圍籬有可能位在邊界。
<br />

### 輸入說明

輸入包含兩行
- 第一行有一個正整數 $n$
- 第二行有 $n$ 個以空隔分隔的整數 $h[1], h[2], \dots, h[n]$

數字範圍
- $3 \leq n \leq 100$
- $0 \leq h[n] \leq 100$

子題配分
- 60%：$n = 3$
- 40%：無額外限制

<br />

### 輸出說明

輸出一個正整數表示新增的圍籬長度總和
<br />

### 範例一：輸入

3
2 0 4

### 範例一：正確輸出

2

<br />

### 範例二：輸入

9
0 5 3 0 6 4 0 1 0

### 範例二：正確輸出

10

<br />

## Python 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 20 ms，使用記憶體最多約為 3.3 MB，通過測試。

n = int(input())  # 讀取圍籬數量n
h = list(map(int, input().split()))  # 讀取圍籬高度h
ans = 0  # 要修補的圍籬高度

for i in range(n):  # 依序檢查每一片圍籬
    if h[i] == 0:   # 如果圍籬高度為0
        if i == 0: ans += h[i+1]  # 如果是第0片，取第1片的高度補上
        elif i == n-1: ans += h[i-1]  # 如果是第n-1片，取第n-2片的高度補上
        else: ans += min(h[i-1], h[i+1])  # 中間的圍籬，取兩側圍籬較低的高度補上

print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

用 Python 程式碼版本1改寫成 C++ 程式碼，於 ZeroJudge 測試結果，最長運算時間約為 3 ms，使用記憶體最多約為 336 kB，通過測試。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;  // 讀取圍籬數量n
    int h[n];
    for(int i=0; i<n; i++) cin >> h[i];  // 讀取圍籬高度h
    int ans = 0;  // 要修補的圍籬高度

    for(int i=0; i<n; i++) {  // 依序檢查每一片圍籬
        if (h[i] == 0) {   // 如果圍籬高度為0
            if (i == 0) ans += h[i+1];  // 如果是第0片，取第1片的高度補上
            else if (i == n-1) ans += h[i-1];  // 如果是第n-1片，取第n-2片的高度補上
            else ans += min(h[i-1], h[i+1]);  // 中間的圍籬，取兩側圍籬較低的高度補上
        }
    }

    cout << ans << endl;  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`