To avoid hurting feelings among friends due to uneven distribution, you decide to evenly distribute these N gifts by category as much as possible. That means for each category of gifts, only multiples of K will be allocated for distribution.
為了避免朋友間因分配不均，互相比較而受傷害，
你決定將這 N 個禮物依照類別，對於每種類別盡可能地平均分配。
也就是對於每種類別的禮物，都只會取 K 的整數倍數量做分配。
For example, let's say N = 12, and K = 3. The categories of the N gifts are {1, 8, 8, 4, 8, 8, 4, 1, 8, 4, 8, 8}. After calculation, there are a total of 2 gifts from category 1, 3 gifts from category 4, and 7 gifts from category 8.
For three people, each can receive a maximum of:
0 gifts of category 1
1 gift of category 4
2 gifts of category 8
So, each person can receive a maximum of 0 + 1 + 2 = 3 gifts.
Given N, K, and the sequence of gift categories {C0, C1, …, CN-1}, please assist in calculating the maximum number of gifts each person can receive without causing harm to anyone.
And thus, in a world where nobody gets hurt (except for your brainpower), the task is completed.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two positive integers, N and K, representing the total number of gifts and the number of friends, respectively.
1 ≤ N ≤ 10^6 1 ≤ K ≤ max(2, N/50) The second line consists of N integers from left to right, denoted as Ci, representing the categories of the gifts. 0 ≤ Ci ≤ 100 | The maximum number of gifts each person can receive under even distribution. |
| 12 3 1 8 8 4 8 8 4 1 8 4 8 8 | 3 |
| 8 2 99 7 7 7 99 50 50 7 | 4 |
Thought Process
Use a map to record the occurrence of each type of gift, named MAP. Then, iterate through the MAP using a for loop (for (auto it : MAP)). Declare a variable ans initialized to 0, and in each iteration, update ans += it.second / K.
Sample Code－ZeroJudge I791: Giving Presents
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, K, ans = 0;
cin >> N >> K;
map<int, int>MAP;
for (int i = 0; i<N; i++) {
int tmp;
cin >> tmp;
MAP[tmp]++;
}
for (auto it:MAP) {
ans += it.second / K;
}
cout << ans << "\n";
}
//ZeroJudge I791
//Dr. SeanXD