Editorial for 購物車 (APCS 2020-07 初級)


簡潔題意

第一行給兩個商品編號 \(a\)、\(b\),第二行給客人數 \(n\)。接下來每位客人一行購物車紀錄:正數 \(x\) 表示放入一個商品 \(x\)、負數 \(-x\) 表示取出一個商品 \(x\),每行以一個 \(0\) 結尾。一位客人「有購買」商品 \(x\),表示 \(x\) 放入的次數嚴格多於取出的次數。輸出同時購買了 \(a\) 與 \(b\) 的客人數。(\(1 \le a, b \le 100\) 且 \(a \ne b\)、\(1 \le n \le 100\);紀錄裡除結尾 \(0\) 外都是非 \(0\) 整數、絕對值不超過 \(100\),而且保證是合法的購物車操作——不會取出購物車裡沒有的商品)

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

  • 子題組 1(\(50\) 分):每行恰好 \(2\) 個正整數+結尾 \(0\)(沒有取出的動作)。
  • 子題組 2(\(50\) 分):無額外限制。

先拿下子題組 1(50 分):每行固定三個數,直接比對

子題組 1 保證每位客人就是「放兩個商品、結束」——不用計數、不用管取出。這位客人同時買了 \(a\) 和 \(b\),意思就是那兩個數恰好是 \(a\) 和 \(b\),兩種順序(先 \(a\) 後 \(b\)、先 \(b\) 後 \(a\))用 || 串起來(3.3)就翻譯完了。

動手前注意兩件讀入的事:

  • 輸入順序是第一行 \(a\)、\(b\),第二行才是 \(n\)——跟很多題目「先給 \(n\)」相反,照題目的順序讀。
  • 每行結尾的 \(0\) 也要讀走(讀進一個變數放著不用就好);漏讀的話,它會被當成下一位客人的資料,後面全部錯位。
#include <iostream>
using namespace std;

int main() {
    int a, b, n;
    cin >> a >> b >> n;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x, y, z;
        cin >> x >> y >> z;  // 子題組 1 保證:每行恰好兩個正整數+一個結尾 0
        if ((x == a && y == b) || (x == b && y == a)) {
            ans = ans + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

範例 1 的每一行剛好都是這種形狀,可以直接拿它驗這一版;範例 2 會 WA 是正常的——它有取出的動作。APCS 逐筆給分,這一版穩拿子題組 1 的 \(50\) 分。

從 50 分到 100 分:讀到 0 為止+兩個計數器

一般情況的紀錄長度不固定,這正是語法書 4.8 教的輸入模式「讀到特定值就停止」——while (cin >> x && x != 0),跟課本的寫法一模一樣(做過 4.8 的配套題〈讀到 0 的最大最小值〉的話,這裡零成本)。另外,cin >> 只認數字、不認「行」,所以完全不用煩惱怎麼「一行一行讀」——每位客人的邊界就是那個結尾 \(0\),讀到它就換下一位。

計數的部分,每位客人只需要兩個計數器cntAcntB 記商品 \(a\)、\(b\) 的「淨次數」(放入加一、取出減一),別的商品跟答案無關、讀過就丟。把計數器宣告在客人迴圈裡面——區域變數出了區塊就銷毀(3.8)、下一位客人重新宣告自動從 \(0\) 開始,「上一位客人的紀錄殘留到下一位」這種 bug 從結構上就不可能發生。最後判斷「有購買」要用嚴格大於 \(0\):放 \(2\) 次取 \(2\) 次是沒買(範例 2 的第二位客人專門示範這件事)。完整程式:

#include <iostream>
using namespace std;

int main() {
    int a, b, n;
    cin >> a >> b >> n;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int cntA = 0, cntB = 0;  // 這位客人 a、b 的淨次數(宣告在迴圈裡,每位自動從 0 開始)
        int x;
        while (cin >> x && x != 0) {
            if (x == a) cntA = cntA + 1;    // 放入一個 a
            if (x == -a) cntA = cntA - 1;   // 取出一個 a
            if (x == b) cntB = cntB + 1;    // 放入一個 b
            if (x == -b) cntB = cntB - 1;   // 取出一個 b
        }
        if (cntA > 0 && cntB > 0) {
            ans = ans + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

四個 if 是刻意寫成獨立的、不用 else if 串起來:題目保證 \(a \ne b\),一個 x 最多只符合其中一個條件,串不串結果都一樣;分開寫的好處是,連「\(a\)、\(b\) 剛好相同」都自動正確(兩個計數器一起動),少一個要自己腦補的前提。

另外提醒一件事:題目保證紀錄是合法的購物車操作——不會取出購物車裡沒有的商品,所以任何時候取出次數都不會超過放入次數,cntAcntB 不可能變成負的。也就是說,這題把判斷寫成 cntA != 0 剛好也會對。但「有購買」的定義是放入次數比取出次數多,照定義寫 > 0 才是真的在回答題目問的事;寫 != 0 是靠「負的不會發生」這個保證撐著,等於多背一個前提——題目哪天沒有這條保證,它立刻就是錯的。

拿範例 2 走一遍(\(a = 3\)、\(b = 9\)):第一位客人 3 9 -3 3 9,商品 \(3\) 的淨次數 \(+1-1+1 = 1\)、商品 \(9\) 是 \(+2\),兩個都大於 \(0\) → 算他一位;第二位客人 3 3 -3 -3 9,商品 \(3\) 淨次數 \(0\) → 沒買 \(3\),不算。輸出 1,跟範例一致。

測過再交:範例缺了「只買其中一個」的客人

盤點兩個範例:範例 1 全是單純的「放兩個商品」,範例 2 才有取出的動作,也示範了「放 \(2\) 次取 \(2\) 次=淨次數 \(0\)=沒買」。但是「只買了其中一個商品」的客人、「取出的是其他商品」的紀錄,兩個範例裡都沒出現過。自己補這四筆:

餵什麼 正確輸出 這一筆在測什麼
1 811 0 0 只買了 \(a\)、\(b\) 連出現都沒出現——兩個要同時成立才算數
1 811 8 -8 0 0 \(8\) 放進去又拿出來、淨次數 \(0\)——出現過不等於有買
1 818 -8 8 1 0 1 拿出來之後又放回去:\(8\) 的淨次數是 \(1\),有買
1 821 5 -5 8 01 8 0 2 取出的是無關商品 \(5\),不能干擾 \(a\)、\(b\) 的計數;兩位都算

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

常犯錯誤
  1. 計數器宣告在迴圈外、忘了每位客人歸零:範例 1 當場抓到——每位客人都繼承前面客人的紀錄,第一位買過 \(a\)、\(b\) 之後,後面每一位都被誤判成有買,會印 5(正確是 2)。像主文那樣宣告在迴圈裡面最省心。
  2. 把「讀到 \(0\) 停」寫成「正數才繼續」while (cin >> x && x > 0)):讀到第一個負數就停了,這位客人剩下的紀錄全部被當成下一位客人的資料,從此整份輸入錯位——範例 2 會印 2(正確是 1)。\(0\) 是「這位客人結束」的訊號、負數是「取出」的動作,兩件事別混在一起。
  3. 忽略取出(讀到負數直接跳過、沒把次數扣回來):範例 2 的第一位客人商品 \(3\) 會被算成放了 \(2\) 次、第二位也一樣,兩位都被誤判有買——印 2(正確是 1)。
  4. 「有出現過就算買」:範例 2 的第二位客人(商品 \(3\) 放 \(2\) 次取 \(2\) 次)專門考這個——出現過但淨次數是 \(0\),其實沒買;這樣寫會印 2(正確是 1)。自測表第 \(2\) 列也專門堵這一條(和上一條),正確輸出 0、這樣寫會印 1
  5. 子題組 1 那一版只判一種順序(只寫 if (x == a && y == b)、漏掉先 \(b\) 後 \(a\)):範例 1 自己就會抓到——第 \(4\) 位客人是 8 1,順序相反卻一樣算有買,漏掉的話印 1(正確是 2)。
  6. 把「同時購買」寫成 ||if (cntA > 0 || cntB > 0)):只買一個也被算進去,範例 2 會印 2(正確是 1);自測表第 \(1\) 列也會現形(印 1、正確是 0)。題目問的是兩個都買,用 &&