Xiaomei owns N cosmetic stores, each with different products and varying popularity. To save the less popular stores, she conducted an online survey to collect the favorite product numbers from customers. After identifying the most popular product numbers from the customers, she plans to place the most popular product in the least popular store for sale.
Xiaomei believes that the number that appears the most in the survey is the most popular product number. The popularity of each store is determined by the total number of times the products it stocks appear in the survey.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two numbers K (1 ≤ K ≤ 10^6) and N (2 ≤ N ≤ 100). K represents the number of collected surveys, and N represents the number of cosmetic stores Xiaomei owns.
The second line contains K numbers R (1 ≤ R ≤ 1000), each representing a product number that customers indicated as their favorite in the survey. The third line contains N numbers Mi (1 ≤ Mi ≤ 1000), each representing the number of products stocked in each store. Following this, there are N lines, each containing Mi numbers S (1 ≤ S ≤ 1000), indicating the product numbers stocked in store i. It is guaranteed that all stores have unique products, and there is only one most popular product number and one least popular store. | Output two numbers: the first number is the most popular product number, and the second number is the least popular store number. |
| 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 |
Thought Process
Use a Map to record the popularity of each product and determine the most popular product while collecting the data.
Calculate the total popularity of each product while collecting the product numbers for each store and determine the minimum value.
Sample Code－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