修補圍籬 題解|APCS 2021 年 11 月初級 第 1 題
簡潔題意
寬度 \(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;
}
測過再交:範例沒考「兩端同時斷」
兩個範例蓋到了「中間斷」「左邊界斷」「右邊界斷」,但有兩種局面沒出現:最左和最右同時斷、以及完全沒有斷。自己補測一下:
| 輸入 | 正確輸出 | 在測什麼 |
|---|---|---|
3 / 0 5 0 |
10 |
兩端同時斷:兩片都要算,各填 \(5\) |
3 / 5 3 7 |
0 |
完全沒斷:什麼都不用填 |
5 / 9 0 1 0 9 |
2 |
兩片斷籬共用同一個好鄰居,各填 \(1\) |
三個都親眼看過正確,這題就穩了。
常犯錯誤
- 「較小」寫成「較大」:範例 1 當場現形(印
4,正確是2)。 - 只處理中間、忘了兩端:範例 1 剛好只有中間斷、照樣過;範例 2 會現形(印
4,正確是10)。 - 子題組 1 用
else if串三個檢查:兩端同時斷時只算到左邊那片。範例 1 照樣過,範例 2 本來就超出子題組 1、看不出差別——自測表第一列就是為它設計的(會印5,正確是10)。 - 往右滑的兩行寫反(先
mid = right;再left = mid;):left也跟著變成剛讀進來的那片,真正的左鄰居就丟了。範例 1 照樣過;範例 2 會現形(印5,正確是10)。