Editorial for 修補圍籬 (APCS 2021-11 初級)

簡潔題意

寬度 \(n\) 的圍籬，高度 \(0\) 代表被吹斷。每片斷掉的圍籬，要填上「左右鄰居中較小」的高度；斷在邊界時只有一個鄰居，就填那一側的高度。保證不會有兩片相鄰的圍籬同時斷掉。求填上去的高度總和（\(3 \le n \le 100\)、\(0 \le h[i] \le 100\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(60\) 分）：\(n = 3\)。
  • 子題組 2（\(40\) 分）：無額外限制。

先拿下子題組 1（\(60\) 分）：三片圍籬，if 就寫得完

\(n = 3\) 時圍籬只有三片，讀成三個變數 a、b、c 就好，連迴圈都不用——只用到語法書上冊第三單元為止的語法。三片各自檢查一次：

  • a 斷了：它在最左邊，只有右鄰居 b，填 b。
  • b 斷了：左右鄰居是 a 和 c，填較小的那個。
  • c 斷了：只有左鄰居 b，填 b。

有一個地方要小心：a 和 c 可能同時斷掉——它們一個在最左、一個在最右，中間隔著 b，不算相鄰，所以「不會有相鄰的兩片同時斷」擋不住這種情況。三個檢查要寫成三個獨立的 if，不能用 else if 串起來（串起來的話，發現 a 斷掉就不會再看 c 了）。

反過來，「保證不相鄰」給了你一個方便：b 斷了的話，跟它相鄰的 a、c 一定是好的——要參考的鄰居永遠不會也是 \(0\)，直接拿來用就對了。

#include <iostream>
using namespace std;

int main() {
    int n, a, b, c;
    cin >> n;              // 子題組 1 保證 n = 3
    cin >> a >> b >> c;

    int cost = 0;
    if (a == 0) {          // 最左片斷了：只有右鄰居 b
        cost += b;
    }
    if (b == 0) {          // 中間斷了：填左右較小的那個
        if (a < c) {
            cost += a;
        } else {
            cost += c;
        }
    }
    if (c == 0) {          // 最右片斷了：只有左鄰居 b
        cost += b;
    }
    cout << cost << endl;
    return 0;
}

範例 2 的 \(n = 9\)，這支程式只讀了前三片，答案會是錯的——這是正常的：APCS 逐筆給分，這一版穩穩拿下子題組 1 的 \(60\) 分。

從 \(60\) 分到 \(100\) 分：讓「三片一組」滑過整排圍籬

\(n\) 變大之後，觀察一件事：判斷一片圍籬要不要填、填多少，需要看的永遠只有它自己和左右鄰居——一次三片。所以把子題組 1 的三個變數改名成 left、mid、right，讓它們沿著圍籬往右滑：每一輪讀進新的一片當 right，檢查夾在中間的 mid，然後整組往右滑一格（left = mid; mid = right;）。

最左片和最右片只有一個鄰居，放在迴圈外面單獨檢查：進迴圈前 left 就是最左片；迴圈跑完時 mid 剛好停在最右片。

這一版新增的語法只有第四單元的單層 for——仍然不需要陣列。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int left, mid, right;   // 相鄰三片圍籬，會沿著整排往右滑
    cin >> left >> mid;

    int cost = 0;
    if (left == 0) {        // 最左片斷了：只有右鄰居
        cost += mid;
    }
    for (int i = 3; i <= n; i++) {
        cin >> right;
        if (mid == 0) {     // 中間那片斷了：填左右較小的那個
            if (left < right) {
                cost += left;
            } else {
                cost += right;
            }
        }
        left = mid;         // 三片一起往右滑一格
        mid = right;
    }
    if (mid == 0) {         // 最右片斷了：只有左鄰居
        cost += left;
    }
    cout << cost << endl;
    return 0;
}

學過陣列的話：直接看 h[i - 1] 和 h[i + 1]

滑動的三個變數要在腦中跟著滑，第一次寫難免手忙腳亂。學過第六單元的陣列之後，有一個思考上簡單得多的寫法：把整排圍籬先存下來，第 \(i\) 片斷了就直接看 h[i - 1] 和 h[i + 1]——跟你在紙上想的一模一樣。

跟上一版比，換掉了什麼：

  • 滑動的三個變數 → 一個陣列 h[]（題目講「第幾片」，照慣例多開一格從 1 用起）。
  • 迴圈外的兩段邊界檢查 → i == 1、i == n 兩個判斷，全部收進同一個迴圈。
  • 兩行「取較小」的 if → min()（記得 #include <algorithm>）。
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    int h[105];             // 題目講「第幾片」，多開一格從 1 用起
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    int cost = 0;
    for (int i = 1; i <= n; i++) {
        if (h[i] == 0) {
            if (i == 1) {
                cost += h[2];                    // 最左片：只有右鄰居
            } else if (i == n) {
                cost += h[n - 1];                // 最右片：只有左鄰居
            } else {
                cost += min(h[i - 1], h[i + 1]); // 中間：填較小的那個
            }
        }
    }
    cout << cost << endl;
    return 0;
}

兩種寫法答案完全一樣、都是滿分，不必急著換。差別在題目變大的時候：如果哪天要看的不只左右各一片，陣列版幾乎不用改思路，滑動版就得多養好幾個變數了。

測過再交：範例沒考「兩端同時斷」

兩個範例蓋到了「中間斷」「左邊界斷」「右邊界斷」，但有兩種局面沒出現：最左和最右同時斷、以及完全沒有斷。自己補測一下：

輸入 正確輸出 在測什麼
3 ／ 0 5 0 10 兩端同時斷：兩片都要算，各填 \(5\)
3 ／ 5 3 7 0 完全沒斷：什麼都不用填
5 ／ 9 0 1 0 9 2 兩片斷籬共用同一個好鄰居，各填 \(1\)

三個都親眼看過正確，這題就穩了。

常犯錯誤
  1. 「較小」寫成「較大」：範例 1 當場現形（印 4，正確是 2）。
  2. 只處理中間、忘了兩端：範例 1 剛好只有中間斷、照樣過；範例 2 會現形（印 4，正確是 10）。
  3. 子題組 1 用 else if 串三個檢查：兩端同時斷時只算到左邊那片。兩個範例都矇得過——自測表第一列就是為它設計的。
  4. 陣列版先寫中間的公式、忘了先擋邊界：i = 1 時會去讀 h[0]（從來沒放過東西的格子），這是未定義行為——可能矇過，也可能翻車。