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\),讀到它就換下一位。
計數的部分,每位客人只需要兩個計數器:cntA、cntB 記商品 \(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\) 剛好相同」都自動正確(兩個計數器一起動),少一個要自己腦補的前提。
另外提醒一件事:題目保證紀錄是合法的購物車操作——不會取出購物車裡沒有的商品,所以任何時候取出次數都不會超過放入次數,cntA、cntB 不可能變成負的。也就是說,這題把判斷寫成 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 8/1/1 0 |
0 |
只買了 \(a\)、\(b\) 連出現都沒出現——兩個要同時成立才算數 |
1 8/1/1 8 -8 0 |
0 |
\(8\) 放進去又拿出來、淨次數 \(0\)——出現過不等於有買 |
1 8/1/8 -8 8 1 0 |
1 |
拿出來之後又放回去:\(8\) 的淨次數是 \(1\),有買 |
1 8/2/1 5 -5 8 0/1 8 0 |
2 |
取出的是無關商品 \(5\),不能干擾 \(a\)、\(b\) 的計數;兩位都算 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 計數器宣告在迴圈外、忘了每位客人歸零:範例 1 當場抓到——每位客人都繼承前面客人的紀錄,第一位買過 \(a\)、\(b\) 之後,後面每一位都被誤判成有買,會印
5(正確是2)。像主文那樣宣告在迴圈裡面最省心。 - 把「讀到 \(0\) 停」寫成「正數才繼續」(
while (cin >> x && x > 0)):讀到第一個負數就停了,這位客人剩下的紀錄全部被當成下一位客人的資料,從此整份輸入錯位——範例 2 會印2(正確是1)。\(0\) 是「這位客人結束」的訊號、負數是「取出」的動作,兩件事別混在一起。 - 忽略取出(讀到負數直接跳過、沒把次數扣回來):範例 2 的第一位客人商品 \(3\) 會被算成放了 \(2\) 次、第二位也一樣,兩位都被誤判有買——印
2(正確是1)。 - 「有出現過就算買」:範例 2 的第二位客人(商品 \(3\) 放 \(2\) 次取 \(2\) 次)專門考這個——出現過但淨次數是 \(0\),其實沒買;這樣寫會印
2(正確是1)。自測表第 \(2\) 列也專門堵這一條(和上一條),正確輸出0、這樣寫會印1。 - 子題組 1 那一版只判一種順序(只寫
if (x == a && y == b)、漏掉先 \(b\) 後 \(a\)):範例 1 自己就會抓到——第 \(4\) 位客人是8 1,順序相反卻一樣算有買,漏掉的話印1(正確是2)。 - 把「同時購買」寫成
||(if (cntA > 0 || cntB > 0)):只買一個也被算進去,範例 2 會印2(正確是1);自測表第 \(1\) 列也會現形(印1、正確是0)。題目問的是兩個都買,用&&。