大眾運輸最省方案 題解|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\) 筆。