大眾運輸最省方案 題解|APCS 2026 年 6 月初級 第 3 題


簡潔題意

公車每趟 \(P_b\) 元、捷運每趟 \(P_m\) 元;同一天連續兩趟的交通工具不同時,第二趟少付 \(D\) 元。也可以買 \(P_t\) 元的一日票,當天不用再付車資。共 \(N\) 天,第 \(i\) 天依序搭 \(K_i\) 趟(\(1\) 是公車、\(2\) 是捷運)。每天選比較便宜的方案,一樣貴就買一日票。輸出總花費與一日票的張數。(\(N \le 100\),\(K_i \le 1000\))

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

  • 子題組 1(\(60\) 分):\(N = 1\) 且 \(K_1 = 5\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下 60 分:只有一天

用 4.3 的 for 一趟一趟讀,single 記單程計費的總額:公車加 \(P_b\)、捷運加 \(P_m\)。轉乘優惠要和上一趟比,所以多一個變數 prev 記上一趟搭什麼;第一趟沒有上一趟,prev 先設成 \(0\)(不是 \(1\) 也不是 \(2\))。這一趟和 prev 不同、而且 prev 不是 \(0\),就扣 \(D\)。

整天讀完才決定買不買一日票:single >= pt 就買。用 >= 不用 >,因為一樣貴也要選一日票,範例 1 就是在測這件事。

#include <iostream>
using namespace std;

int main() {
    int pb, pm, d, pt;
    cin >> pb >> pm >> d >> pt;
    int n, k;
    cin >> n >> k;  // 子題組 1 保證只有一天
    int single = 0;  // 這一天單程計費的總額
    int prev = 0;    // 上一趟搭什麼;0 代表今天還沒搭過
    for (int i = 1; i <= k; i++) {
        int t;
        cin >> t;
        if (t == 1) single = single + pb;
        else single = single + pm;
        if (prev != 0 && prev != t) single = single - d;  // 和上一趟不同才是轉乘
        prev = t;
    }
    if (single >= pt) cout << pt << " " << 1 << endl;  // 一樣貴也買一日票
    else cout << single << " " << 0 << endl;
    return 0;
}

這個版本對範例 2(\(3\) 天)會 WA 是正常的;它對子題組 1 的 \(12\) 筆測資全對,穩拿 \(60\) 分。

從 60 分到 100 分:外面再包一層「每一天」

把一天的計算放進 4.6 的巢狀迴圈:外層跑 \(N\) 天,每天的結果加進總花費。

single 和 prev 要每天重新開始:轉乘優惠只算同一天,前一天的最後一趟和今天的第一趟沒有關係。把這兩個變數宣告在外層迴圈的大括號裡面(3.9 的區塊),每一天開始時都會重新設成 \(0\)。

數字範圍:一天最多 \(1000\) 趟、每趟最多 \(10^4\) 元,single 最多 \(10^7\);每天最多付 \(P_t \le 10^4\) 元,總花費最多 \(10^6\),int 都夠。

#include <iostream>
using namespace std;

int main() {
    int pb, pm, d, pt;
    cin >> pb >> pm >> d >> pt;
    int n;
    cin >> n;
    int total = 0;   // n 天的總花費
    int passes = 0;  // 買了幾次一日票
    for (int day = 1; day <= n; day++) {
        int k;
        cin >> k;
        int single = 0;  // 宣告在迴圈裡:每一天都從 0 開始
        int prev = 0;    // 每一天的第一趟都沒有「上一趟」
        for (int i = 1; i <= k; i++) {
            int t;
            cin >> t;
            if (t == 1) single = single + pb;
            else single = single + pm;
            if (prev != 0 && prev != t) single = single - d;
            prev = t;
        }
        if (single >= pt) {
            total = total + pt;
            passes = passes + 1;
        } else {
            total = total + single;
        }
    }
    cout << total << " " << passes << endl;
    return 0;
}

測過再交:範例每天都至少搭兩趟

輸入 預期輸出 在測什麼
10 20 5 100/2/1/1/1/2 30 0 每天只搭一趟;跨天不算轉乘
10 20 5 100/1/3/1 2 1 30 0 每一趟都和上一趟比:\(10 + 15 + 5\)
10 20 5 25/1/4/1 1 1 1 25 1 一天搭完才決定買不買一日票

這幾筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 每搭一趟就檢查一次要不要買一日票:同一天會被算成買了好幾張。範例全過;10 20 5 25/1/4/1 1 1 1 的答案是 25 1,會印出 50 2。本站 \(20\) 筆掛 \(14\) 筆。
  • prev 沒有每天重設:前一天最後一趟和今天第一趟不同時,被當成轉乘。範例全過;10 20 5 100/2/1/1/1/2 的答案是 30 0,會印出 25 0。本站 \(20\) 筆掛 \(2\) 筆。
  • 每一趟都和當天第一趟比,而不是和上一趟比:範例全過;10 20 5 100/1/3/1 2 1 的答案是 30 0,會印出 35 0。本站 \(20\) 筆掛 \(1\) 筆。
  • 以為每天至少搭兩趟,一開始就先讀兩個數:某天只搭一趟時,會把下一天的資料讀進來。範例全過;10 20 5 100/2/1/1/1/2 的答案是 30 0,會印出 40 0。本站 \(20\) 筆掛 \(2\) 筆。