ZeroJudge 解題筆記：>n632. 熱門商品 (Commodity)

作者：王一哲
日期：2025年6月10日


ZeroJudge 題目連結：n632. 熱門商品 (Commodity)

解題想法

因為商品的編號不連續，用字典計數比較方便，在 Python 中可以用預設的字典，也可以用 collections 函式庫中的 defaultdict 或 Counter，由於這題要找問卷中出現最多次的商品編號，用 Counter.most_common() 最方便。在 C++ 可以用 map 或 unordered_map，因為資料不需要排序，用 unordered_map 會比較快一點。

Python 程式碼

寫法1，使用預設的 dict。使用時間約為 0.8 s，記憶體約為 78.4 MB，通過測試。

import sys

for line in sys.stdin:
    K, N = map(int, line.split())  # K 份問卷，N 家商店
    cnt = dict()  # 問卷計數器
    for i in map(int, input().split()):  # 讀取問卷資料
        if i not in cnt: cnt[i] = 1  # 如果 i 不在 cnt 之中，cnt[i] 設定為 1
        else: cnt[i] += 1  # 如果 i 在 cnt 之中，cnt[i] 加 1
    popular = max([(v, k) for k, v in cnt.items()])[1]  # 最受歡迎的商品
    _ = tuple(map(int, input().split()))  # 每家商店的商品數量，用不到
    shop, imin = 0, float('inf')  # 積分最低的商店編號及分數
    for i in range(1, N+1):  # 依序讀取 N 家商店
        score = 0  # 積分
        for j in map(int, input().split()):  # 依序讀取這家商店販賣的商品
            if j in cnt: score += cnt[j]  # 如果有出現在問卷中，分數加 cnt[j]
        if score < imin:  # 更新 shop 及 imin
            shop = i; imin = score
    print(popular, shop)  # 印出答案

寫法2，使用 collections 函式庫中的 defaultdict。使用時間約為 0.6 s，記憶體約為 80.3 MB，通過測試。

import sys
from collections import defaultdict

for line in sys.stdin:
    K, N = map(int, line.split())  # K 份問卷，N 家商店
    cnt = defaultdict(int)  # 問卷計數器
    for i in map(int, input().split()):  # 讀取問卷資料
        cnt[i] += 1  # cnt[i] 加 1
    popular = max([(v, k) for k, v in cnt.items()])[1]  # 最受歡迎的商品
    _ = tuple(map(int, input().split()))  # 每家商店的商品數量，用不到
    shop, imin = 0, float('inf')  # 積分最低的商店編號及分數
    for i in range(1, N+1):  # 依序讀取 N 家商店
        score = 0  # 積分
        for j in map(int, input().split()):  # 依序讀取這家商店販賣的商品
            score += cnt[j]  # 分數加 cnt[j]
        if score < imin:  # 更新 shop 及 imin
            shop = i; imin = score
    print(popular, shop)  # 印出答案

寫法3，使用 collections 函式庫中的 Counter。使用時間約為 0.5 s，記憶體約為 81.1 MB，通過測試。

import sys
from collections import Counter

for line in sys.stdin:
    K, N = map(int, line.split())  # K 份問卷，N 家商店
    cnt = Counter(map(int, input().split()))  # 問卷計數器
    popular = cnt.most_common(1)[0][0]  # 最受歡迎的商品
    _ = tuple(map(int, input().split()))  # 每家商店的商品數量，用不到
    shop, imin = 0, float('inf')  # 積分最低的商店編號及分數
    for i in range(1, N+1):  # 依序讀取 N 家商店
        score = 0  # 積分
        for j in map(int, input().split()):  # 依序讀取這家商店販賣的商品
            if j in cnt: score += cnt[j]  # 如果有出現在問卷中，分數加 cnt[j]
        if score < imin:  # 更新 shop 及 imin
            shop = i; imin = score
    print(popular, shop)  # 印出答案

C++ 程式碼

寫法1，使用 map。使用時間約為 0.1 s，記憶體約為 368 kB，通過測試。

#include <cstdio>
#include <map>
using namespace std;

int main() {
    int K, N;  // K 份問卷，N 家商店
    while(scanf("%d %d", &K, &N) != EOF) {
        map<int, int> cnt;  // 問卷計數器
        for(int i=0; i<K; i++) {  // 讀取問卷資料
            int R; scanf("%d", &R);  // 問卷中的商品編號
            cnt[R]++;  // cnt[R] 加 1
        }
        int popular = 0, imax = 0;  // 最受歡迎的商品
        for(auto it : cnt) {  // 依序讀取 cnt 的資料
            if (it.second > imax) {  // 如果 it.second 大於 imax
                popular = it.first;  // 更新 popular
                imax = it.second;  // 更新 imax
            }
        }
        int M[N+1];  // 每家商店的商品數量
        for(int i=1; i<=N; i++) scanf("%d", &M[i]);
        int shop = 0, imin = 1E9;  // 積分最低的商店編號及分數
        for(int i=1; i<=N; i++) {  // 依序讀取 N 家商店
            int score = 0;  // 積分
            for(int j=0; j<M[i]; j++) {  // 依序讀取這家商店販賣的商品
                int S; scanf("%d", &S);  // 商品編號
                score += cnt[S];  // 分數加 cnt[S]
            }
            if (score < imin) {  // 更新 shop 及 imin
                shop = i; imin = score;
            }
        }
        printf("%d %d\n", popular, shop);  // 印出答案
    }
    return 0;
}

寫法2，使用 unordered_map。使用時間約為 0.1 s，記憶體約為 304 kB，通過測試。

#include <cstdio>
#include <unordered_map>
using namespace std;

int main() {
    int K, N;  // K 份問卷，N 家商店
    while(scanf("%d %d", &K, &N) != EOF) {
        unordered_map<int, int> cnt;  // 問卷計數器
        for(int i=0; i<K; i++) {  // 讀取問卷資料
            int R; scanf("%d", &R);  // 問卷中的商品編號
            cnt[R]++;  // cnt[R] 加 1
        }
        int popular = 0, imax = 0;  // 最受歡迎的商品
        for(auto it : cnt) {  // 依序讀取 cnt 的資料
            if (it.second > imax) {  // 如果 it.second 大於 imax
                popular = it.first;  // 更新 popular
                imax = it.second;  // 更新 imax
            }
        }
        int M[N+1];  // 每家商店的商品數量
        for(int i=1; i<=N; i++) scanf("%d", &M[i]);
        int shop = 0, imin = 1E9;  // 積分最低的商店編號及分數
        for(int i=1; i<=N; i++) {  // 依序讀取 N 家商店
            int score = 0;  // 積分
            for(int j=0; j<M[i]; j++) {  // 依序讀取這家商店販賣的商品
                int S; scanf("%d", &S);  // 商品編號
                score += cnt[S];  // 分數加 cnt[S]
            }
            if (score < imin) {  // 更新 shop 及 imin
                shop = i; imin = score;
            }
        }
        printf("%d %d\n", popular, shop);  // 印出答案
    }
    return 0;
}