串燒
統計每種串燒的訂購量與送餐量，確認漏上與多上的數量。
01 / 題目理解
DESCRIPTION
確認串燒是否漏上或多上
共有 M 個人到串燒店用餐，每個人各自點了一些串燒，但送餐後所有串燒混在一起。請根據大家的訂單，計算店家漏上了幾個，以及多送了幾個。
INPUT
第一行輸入送上的串燒數量 N 與人數 M。第二行輸入 N 個送上的品項編號。接下來 M 行，每行先輸入該客人的訂購數量，再輸入各品項編號。
OUTPUT
輸出兩個整數，依序表示漏上的串燒數量與多上的串燒數量。
CONSTRAINTS
1 ≤ N ≤ 10000、1 ≤ M ≤ 10。每個品項編號介於 1 到 100 之間，每位客人訂購 1 到 100 個串燒。
02 / 解題思路
01
統計送餐數量
使用 delivered 陣列，依品項編號記錄店家實際送上的數量。
02
統計訂購數量
讀取每位客人的明細，將相同品項的數量累加到 ordered 陣列。
03
比較每個品項
若訂購量大於送餐量，差值就是漏上的數量；反之，差值就是多上的數量。最後將所有品項的差值分別加總。
03 / 範例分析
EXAMPLE 1
送上 5 個品項 1、4 個品項 2 和 1 個品項 4；實際訂購 4 個品項 1、4 個品項 2 和 2 個品項 3。因此品項 3 漏了 2 個，品項 1 與品項 4 各多了 1 個，答案為 2 2。
04 / C++ 實作
SOLUTION / P918.CPPCOUNTING
#include <iostream>
using namespace std;
int main() {
int n, m;
int delivered[101] = {}, ordered[101] = {};
cin >> n >> m;
for (int i = 0; i < n; ++i) {
int item;
cin >> item;
++delivered[item];
}
for (int person = 0; person < m; ++person) {
int quantity;
cin >> quantity;
for (int i = 0; i < quantity; ++i) {
int item;
cin >> item;
++ordered[item];
}
}
int missing = 0;
int extra = 0;
for (int item = 1; item <= 100; ++item) {
if (ordered[item] > delivered[item]) {
missing += ordered[item] - delivered[item];
} else {
extra += delivered[item] - ordered[item];
}
}
cout << missing << ' ' << extra << '\n';
return 0;
}05 / 複雜度分析
讀取所有資料需要 O(N + \sum P_j)，最後只需檢查 100 種品項，因此總時間複雜度為 O(N + \sum P_j + 100)。兩個陣列的大小固定為 101，空間複雜度為 O(100)。