Editorial for 購買力 (APCS 2021-01 初級)
簡潔題意
\(n\) 個商品,每個商品有近三天的價格。一個商品近三天最高價與最低價的差距至少 \(d\) 就把它買下來,費用是那三天價格的平均。輸出買了幾個商品、總共花了多少錢(\(1 \le n \le 100\)、\(0 \le d \le 100\)、價格都是 \(0\) 到 \(100\) 的整數,而且題目保證被買下的商品三天平均會是整數)。
依正確通過的測試資料筆數給分,其中:
- 第 1 子題組(\(50\) 分):\(n = 1\)。
- 第 2 子題組(\(50\) 分):\(1 \le n \le 100\)。
先看懂題目:每個商品各自算,互不影響
一個商品要不要買、要花多少錢,只看它自己那三天的價格,跟別的商品完全沒有關係。所以整題就是把同一件事重複做 \(n\) 次:
- 讀進三個價格。
- 找出這三天的最高價和最低價,相減就是價差。
- 價差至少 \(d\)(也就是 \(\ge d\),等於也算)就買:數量加 \(1\)、花費加上三天的平均。
因為商品彼此不影響,讀一個就處理一個,不必先把全部價格存起來。
先拿下子題組 1(\(50\) 分):只有一個商品
子題組 1 保證 \(n = 1\),整份輸入就只有一個商品的三個價格。剩下的問題只有一個:三個數字裡的最高和最低怎麼找?
用兩個擂台:先假設第一個價格 \(a\) 就是最高的,再讓 \(b\)、\(c\) 依序來挑戰,比它高就換人當紀錄;最低同理。
擂台的初值直接拿 \(a\)——\(a\) 本來就是三個價格之一,所以無論如何都是合法答案的候選。別自己挑一個數字(例如 \(0\))當初值,那要另外證明「一定會被換掉」才安全。
#include <iostream>
using namespace std;
int main() {
int n, d;
cin >> n >> d;
int a, b, c;
cin >> a >> b >> c;
int highest = a; // 先讓 a 當「最高」的紀錄
if (b > highest) highest = b;
if (c > highest) highest = c;
int lowest = a; // 先讓 a 當「最低」的紀錄
if (b < lowest) lowest = b;
if (c < lowest) lowest = c;
if (highest - lowest >= d) {
cout << 1 << ' ' << (a + b + c) / 3 << endl;
} else {
cout << 0 << ' ' << 0 << endl; // 沒買也要印兩個數字
}
return 0;
}
兩個地方容易被忽略:
>=不是>:題目寫「至少 \(d\)」,價差剛好等於 \(d\) 也要買。- 不買的時候也要輸出:印
0 0,不是什麼都不印。
\(n\) 在這個子題組固定是 \(1\),讀進來只是為了把輸入吃完。到這裡用的東西全部落在語法書上冊的前三個單元——讀入輸出、變數、整數除法、if——連迴圈都還沒用到。
交出去之前先自己測三種情況
範例 1 只測到「有買、而且平均剛好整除得很漂亮」,這三種自己補:
| 輸入 | 預期輸出 | 在測什麼 |
|---|---|---|
1 0 / 1 1 1 |
1 1 |
\(d = 0\):價差 \(0\) 也要買;而且平均要三個一起除(分開除會變成 \(0\)) |
1 6 / 10 4 7 |
1 7 |
價差剛好等於 \(d\) |
1 7 / 10 4 7 |
0 0 |
沒買的時候要印 0 0 |
範例 2 會答錯是正常的:它有 \(3\) 個商品,本來就不屬於子題組 1。這支程式只讀第一個商品,對範例 2 會印出 1 33(正確答案是 2 86)。APCS 依正確通過的測試資料筆數給分,子題組 1 的 \(50\) 分照樣穩穩拿到。
從 \(50\) 分到 \(100\) 分:把同一段包進迴圈
商品變多之後,上面那段程式碼一個字都不用改——只要把「讀三個價格、找最高最低、判斷要不要買」整段搬進一個 for 迴圈裡跑 \(n\) 次,再把「印出來」換成兩個累加器(買了幾個、花了多少),迴圈跑完再一次印出:
#include <iostream>
using namespace std;
int main() {
int n, d;
cin >> n >> d;
int bought_count = 0; // 買了幾個商品
int total_cost = 0; // 總共花了多少錢
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
int highest = a;
if (b > highest) highest = b;
if (c > highest) highest = c;
int lowest = a;
if (b < lowest) lowest = b;
if (c < lowest) lowest = c;
if (highest - lowest >= d) {
bought_count++;
total_cost += (a + b + c) / 3;
}
}
cout << bought_count << ' ' << total_cost << endl;
return 0;
}
四個地方值得看清楚:
- 兩個累加器宣告在迴圈外面:它們要記的是「到目前為止」的總和,宣告在迴圈裡面每一輪都會重新歸零。
a、b、c宣告在迴圈裡面:每個商品都是全新的三個價格,用完就不需要了。(a + b + c) / 3要三個加起來再除:這是整數除法,小數會被丟掉,所以a / 3 + b / 3 + c / 3是不一樣的東西。題目保證的是被買下的商品平均會是整數,而我們也只在買的時候才算它。- 不管有沒有買到東西,最後都要印:
bought_count和total_cost從 \(0\) 開始,一個都沒買就自然印出0 0。
(如果已經讀到上冊 7.6,找最高最低那六行可以換成 int highest = max(max(a, b), c); 與 int lowest = min(min(a, b), c);,開頭補一行 #include <algorithm>,其餘完全不變——兩種寫法都是滿分。)
測過再交:範例沒蓋到的四種情況
兩個範例都是「有買到東西、而且不只買一個」。沒被蓋到的自己補:
| 輸入 | 預期輸出 | 在測什麼 |
|---|---|---|
3 0 / 1 1 1 / 2 2 2 / 3 3 3 |
3 6 |
\(d = 0\) 全部都買;平均要三個一起除 |
2 100 / 0 50 100 / 10 20 30 |
1 50 |
價差剛好等於 \(d\),而且有買有不買 |
3 100 / 10 20 30 / 0 0 0 / 50 50 50 |
0 0 |
一個都沒買,還是要印 0 0 |
1 0 / 0 0 0 |
1 0 |
買了、但花費是 \(0\)——別把它跟「沒買」搞混 |
第三列和第四列是這題最容易翻車的兩種局面:一個是「沒買」,一個是「買了但金額是 \(0\)」,它們的輸出完全不同。
這四種都親眼看過正確,這題就穩了。
常犯錯誤
- 價差判斷寫成
> d:題目說「至少 \(d\)」,剛好等於也要買。兩個範例剛好都不是「剛好等於」的情況,所以都矇得過去;子題組 1 那張自測表的第二列1 6/10 4 7一試就現形(會印0 0,正確答案是1 7)。 - 平均寫成
a / 3 + b / 3 + c / 3:整數除法會各自把小數丟掉,先加起來再除才對。兩個範例裡被買下的那些商品,三個價格剛好各自都能被 \(3\) 整除,所以也都矇得過去;子題組 1 那張自測表的第一列1 0/1 1 1會印1 0(正確答案是1 1)。 - 擂台初值自己挑一個數字:
lowest設成 \(0\) 就完蛋了——價格最小就是 \(0\),lowest永遠停在 \(0\),價差會變成「最高價」本身。範例 2 會印3 163(正確答案是2 86)。 - 累加器宣告在迴圈裡面:每一輪都重新歸零,最後印出來的只有最後一個商品的結果。範例 2 會印
0 0。 - 以為三天的價格是由低到高排好的,直接拿第三天減第一天。範例 1 的價格是
24 27 21,第三天反而最低,這樣會印0 0(正確答案是1 24)。 - 沒買到東西時就不輸出:把
cout包進「有買才印」的判斷裡。兩個範例都有買到東西,所以都矇得過去;子題組 1 那張自測表的第三列1 7/10 4 7一試就現形——畫面上一個字都沒有。