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\) 次:

  1. 讀進三個價格。
  2. 找出這三天的最高價最低價,相減就是價差。
  3. 價差至少 \(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;
}

四個地方值得看清楚:

  • 兩個累加器宣告在迴圈外面:它們要記的是「到目前為止」的總和,宣告在迴圈裡面每一輪都會重新歸零。
  • abc 宣告在迴圈裡面:每個商品都是全新的三個價格,用完就不需要了。
  • (a + b + c) / 3 要三個加起來再除:這是整數除法,小數會被丟掉,所以 a / 3 + b / 3 + c / 3 是不一樣的東西。題目保證的是被買下的商品平均會是整數,而我們也只在買的時候才算它。
  • 不管有沒有買到東西,最後都要印bought_counttotal_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\)」,它們的輸出完全不同。

這四種都親眼看過正確,這題就穩了。

常犯錯誤
  1. 價差判斷寫成 > d:題目說「至少 \(d\)」,剛好等於也要買。兩個範例剛好都不是「剛好等於」的情況,所以都矇得過去;子題組 1 那張自測表的第二列 1 6 / 10 4 7 一試就現形(會印 0 0,正確答案是 1 7)。
  2. 平均寫成 a / 3 + b / 3 + c / 3:整數除法會各自把小數丟掉,先加起來再除才對。兩個範例裡被買下的那些商品,三個價格剛好各自都能被 \(3\) 整除,所以也都矇得過去;子題組 1 那張自測表的第一列 1 0 / 1 1 1 會印 1 0(正確答案是 1 1)。
  3. 擂台初值自己挑一個數字lowest 設成 \(0\) 就完蛋了——價格最小就是 \(0\),lowest 永遠停在 \(0\),價差會變成「最高價」本身。範例 2 會印 3 163(正確答案是 2 86)。
  4. 累加器宣告在迴圈裡面:每一輪都重新歸零,最後印出來的只有最後一個商品的結果。範例 2 會印 0 0
  5. 以為三天的價格是由低到高排好的,直接拿第三天減第一天。範例 1 的價格是 24 27 21,第三天反而最低,這樣會印 0 0(正確答案是 1 24)。
  6. 沒買到東西時就不輸出:把 cout 包進「有買才印」的判斷裡。兩個範例都有買到東西,所以都矇得過去;子題組 1 那張自測表的第三列 1 7 / 10 4 7 一試就現形——畫面上一個字都沒有。