Editorial for 巴士站牌 (APCS 2022-10 初級)

簡潔題意

依序經過 \(n\) 個巴士站，相鄰兩站的行進時間是曼哈頓距離 \(|x_1 - x_2| + |y_1 - y_2|\)。輸出所有相鄰兩站行進時間的最大值與最小值，中間以空白隔開（\(4 \le n \le 100\)、\(-100 \le x_i, y_i \le 100\)）。

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

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

先拿下子題組 1（\(60\) 分）：四站三段，if 就寫得完

\(n = 4\) 時只有三段路，把四站座標讀成八個變數，三段距離一段一段算，連迴圈都不用——只用到語法書上冊第三單元為止的語法。

曼哈頓距離裡的絕對值也不需要任何新工具：差是負的就把它變號，一個 if 就是手工版的絕對值。

三段距離都算出來之後，用擂台法選出最大和最小：先讓第一段站上擂台（mx 和 mn 都設成 d1），後面每一段都上來比一次。

#include <iostream>
using namespace std;

int main() {
    int n;                          // 子題組 1 保證 n = 4
    int x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> n;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

    // 站 1 → 站 2：把兩個差都變成正的，加起來就是曼哈頓距離
    int dx = x2 - x1, dy = y2 - y1;
    if (dx < 0) dx = -dx;
    if (dy < 0) dy = -dy;
    int d1 = dx + dy;

    dx = x3 - x2;                   // 站 2 → 站 3
    dy = y3 - y2;
    if (dx < 0) dx = -dx;
    if (dy < 0) dy = -dy;
    int d2 = dx + dy;

    dx = x4 - x3;                   // 站 3 → 站 4
    dy = y4 - y3;
    if (dx < 0) dx = -dx;
    if (dy < 0) dy = -dy;
    int d3 = dx + dy;

    int mx = d1, mn = d1;           // 擂台：先讓第一段站上去
    if (d2 > mx) mx = d2;
    if (d2 < mn) mn = d2;
    if (d3 > mx) mx = d3;
    if (d3 < mn) mn = d3;

    cout << mx << " " << mn << endl;
    return 0;
}

注意一件事：兩個範例剛好都是 \(n = 4\)，這一版兩個範例都會過。但它只讀前四站，\(n\) 再大就不對了——範例全綠不代表滿分，這一版拿到的是子題組 1 的 \(60\) 分。

從 \(60\) 分到 \(100\) 分：記住「上一站」就好

\(n\) 變大之後，發現每一段距離只跟這一站和上一站有關。所以整排座標根本不用全部記住：用 px、py 記住上一站，每讀進一站就算一段距離、跟擂台比一次，然後把「上一站」換成自己。新增的語法只有第四單元的單層 for——不需要陣列。

改用迴圈之後，「先讓第一段站上擂台」不好寫（第一段跟後面每一段長得一樣），改用初值處理：

  • 距離不可能是負的，所以 mx 從 \(0\) 開始，任何一段都能把它往上推。
  • 最小值不能從 \(0\) 開始（\(0\) 會直接霸榜），要放一個比一切可能距離都大的數。座標在 \(-100\) 到 \(100\) 之間，兩個差各最多 \(200\)，一段距離最多 \(400\)——所以 mn 從 \(401\) 開始就安全。
#include <iostream>
using namespace std;

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

    int px, py;                 // 上一站的座標
    cin >> px >> py;

    int mx = 0, mn = 401;       // 擂台初值：距離不可能超過 400、不可能是負的
    for (int i = 2; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        int dx = x - px, dy = y - py;
        if (dx < 0) dx = -dx;   // 把差變成正的（手工絕對值）
        if (dy < 0) dy = -dy;
        int d = dx + dy;
        if (d > mx) mx = d;     // 擂台：更新最大
        if (d < mn) mn = d;     // 擂台：更新最小
        px = x;                 // 這一站變成下一輪的「上一站」
        py = y;
    }
    cout << mx << " " << mn << endl;
    return 0;
}

讀完上冊之後：abs、max、min 各省下一段

上面那版一行都沒有超出前四單元。讀到上冊 7.6 常用內建函式之後，三件手工活都可以交給內建函式：手工絕對值 → abs()（記得 #include <cstdlib>）、兩行擂台 → max() 與 min()（#include <algorithm>）。迴圈的骨架完全相同：

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

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

    int px, py;
    cin >> px >> py;

    int mx = 0, mn = 401;
    for (int i = 2; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        int d = abs(x - px) + abs(y - py);   // abs 住在 <cstdlib>（上冊 7.6）
        mx = max(mx, d);
        mn = min(mn, d);
        px = x;
        py = y;
    }
    cout << mx << " " << mn << endl;
    return 0;
}

兩種寫法答案完全一樣、都是滿分，不必急著換。

測過再交：範例只考了 \(n = 4\)

兩個範例都是 \(n = 4\)、最大最小也都不在第一段。自己補幾筆把缺口蓋掉：

輸入 正確輸出 在測什麼
5 ／ 0 0 0 5 3 5 3 1 -2 1 5 3 \(n > 4\)：子題版在這裡就掛了
4 ／ 2 3 3 3 4 3 5 3 1 1 每段一樣長：最大＝最小，兩個都要對
4 ／ -3 -3 -1 -3 -1 -1 -6 -1 5 2 座標全是負的：絕對值有沒有寫對

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

常犯錯誤
  1. 輸出順序印反：題目要「先最大、再最小」。範例 1 當場現形（印 2 5，正確是 5 2）。
  2. 忘了取絕對值：座標可能是負的，差也可能是負的。範例 1 當場現形（印 5 -1——負的距離直接露出來）。
  3. 最小值初值設 \(0\)：\(0\) 比每一段距離都小，永遠沒人擠得下去。範例 1 當場現形（印 5 0）。
  4. 段數多算一段：\(n\) 站只有 \(n - 1\) 段，迴圈寫成跑 \(n\) 次會去讀不存在的資料，算出一段垃圾距離。範例 1 當場現形（實測印 5 0）。