# 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，通過測試。 ```python= 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，通過測試。 ```cpp= #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++`