小美擁有 N 間化妝品店，每間店擺放的商品不同，受歡迎的程度也不同。為了拯救較不受歡迎的店家，他在網路上進行了一次問卷調查，蒐集各個客戶最喜愛的商品編號。得到客戶們最受歡迎的商品編號後，打算將它擺放在最不受歡迎的商店裡出售。
小美認為，問卷中出現次數最多的數字就是最受歡迎的商品編號，而每間商店的受歡迎程度則為商店內擺放商品在問卷中出現的次數總和。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一列包含兩個數字 K (1 ≤ K ≤ 106) 和 N (2 ≤ N ≤ 100)，K 表示回收了多少份問卷，N 表示小美擁有幾間化妝品店。 第二列包含 K 個數字 R (1 ≤ R ≤ 1000)，分別表示客戶在問卷中回答的商品編號 (即客戶最喜歡的商品編號)。 第三列包含 N 個數字 Mi (1 ≤ Mi ≤ 1000)，分別表示每間店擺放的商品數 量。 接下來有 N 列，每列有 Mi 個數字 S (1 ≤ S ≤ 1000)，表示編號 i 的商店擺放的所有商品編號。 已確保所有店家擺放的商品皆不重複，且只有一個最受歡迎的商品編號和一個最不受歡迎的商店。 | 輸出兩個數字，第一個數字為最受歡迎的商品編號，第二個數字為最不受歡迎的商店編號。 |
| 6 3 56 56 47 23 47 47 1 1 1 23 47 56 | 47 1 |
| 9 4 44 99 44 11 44 69 23 25 69 2 5 4 1 11 25 58 47 22 23 24 7 99 44 12 69 | 44 2 |
解題思路
使用 Map 來紀錄每一個商品的受歡迎程度並且邊收資料邊判斷最受歡迎的商品。
收商店的商品編號時計算每個商品受歡迎程度的總和並且判斷最小值。
範例程式碼－ZeroJudge N632: 熱門商品 (Commodity)
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int K, N;
cin >> K >> N;
int max = -999, max_num = 0;
map<int, int>MAP;
for (int i = 0; i<K; i++)
{
int tmp;
cin >> tmp;
MAP[tmp]++;
if (MAP[tmp] > max)
{
max = MAP[tmp];
max_num = tmp;
}
}
vector<int>M;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
M.push_back(tmp);
}
int min = -1, min_num = 0;
for (int i = 0; i<N; i++)
{
int sum = 0;
for (int j = 0; j<M[i]; j++)
{
int tmp;
cin >> tmp;
sum += MAP[tmp];
}
if (sum < min || min == -1)
{
min = sum;
min_num = i+1;
}
}
cout << max_num << " " << min_num << "\n";
}
//ZeroJudge N632
//Dr. SeanXD