給兩個整數 A 和 B,代表你要觀察的商品編號。
商場在每一位客人的購物車都放置了一個感應器,能夠得知每位客人將商品放入購物車或拿出購物車。感應器存放的紀錄是一連串的整數,一個正整數 x 表示這位客人將一個編號是 x 的商品放入他的購物車,一個負數 -x 表示這位客人將一個編號是
的商品從他的購物車移除。
現在有 N 位客人的購物車紀錄,你想要統計有幾位客人最後有購買商品 A 與商品 B,一個客人有購買商品 X 表示商品 X 在他的購物車中「放入的次數比拿出還多」。
範例測資
範例輸入 | 範例輸出 |
---|---|
第一行有兩個正整數 A 和 B (1 <= A, B <= 100) 第二行有一個正整數 N (1 <= N <= 100),表示客人的數量。 接下來有 N 行,第 i 行表示第 i 位客人的購物車紀錄。 對於每個購物車紀錄包含一連串的整數,最後一個數字必定為 0,表示購物紀錄結尾,其他數字必定為非 0 的整數且絕對值不超過 ,定義同題目敘述。 | 輸出一個整數,表示有幾位客人同時有購買商品 A 與商品 B。 |
1 8 5 1 8 0 5 6 0 2 7 0 8 1 0 33 22 0 | 2 |
3 9 2 3 9 -3 3 9 0 3 3 -3 -3 9 0 | 1 |
解題思路
收購物車資料的時候可以用 EOF,可以用 Map 來紀錄商品的進出,如果放進去就 +1,拿出來就 -1。
收完每個人的資料可以判斷 Map 中的商品 A 和 B 有沒有超過 0,要「A 跟 B 都有買」答案才能 +1。
範例程式碼-ZeroJudge F579: 購物車
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int a, b;
cin >> a >> b;
int N;
cin >> N;
int ans = 0;
for (int i = 0; i<N; i++)
{
int tmp;
map<int, int>MAP;
while (cin >> tmp && tmp != 0)
{
if (tmp > 0) MAP[tmp]++;
else MAP[tmp*-1]--;
}
if (MAP[a] > 0 && MAP[b] > 0) ans++;
}
cout << ans << "\n";
}
//ZeroJudge F579
//Dr. SeanXD