Drinks Choosing
Hazrat Ali
There are n students living in a building, and for each of them the favorite drink ai is known. So you know n integers a1,a2,…,an, where ai (1≤ai≤k) is the type of the favorite drink of the i-th student. The drink types are numbered from 1 to k.
There are infinite number of drink sets. Each set consists of exactly two portions of the same drink. In other words, there are k types of drink sets, the j-th type contains two portions of the drink j. The available number of sets of each of the k types is infinite.
You know that students will receive the minimum possible number of sets to give all students exactly one drink. Obviously, the number of sets will be exactly ⌈n2⌉, where ⌈x⌉ is x rounded up.
After students receive the sets, they will distribute their portions by their choice: each student will get exactly one portion. Note, that if n is odd then one portion will remain unused and the students' teacher will drink it.
What is the maximum number of students that can get their favorite drink if ⌈n2⌉ sets will be chosen optimally and students will distribute portions between themselves optimally?
The first line of the input contains two integers n and k (1≤n,k≤1000) — the number of students in the building and the number of different drinks.
The next n lines contain student's favorite drinks. The i-th line contains a single integer from 1 to k — the type of the favorite drink of the i-th student.
Print exactly one integer — the maximum number of students that can get a favorite drink.
5 3 1 3 1 1 2
4
10 3 2 1 3 2 3 3 1 3 1 2
9
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
map<int, int> cnt;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
cnt[a]++;
}
int full = 0, left = 0;
for (auto [key, value]: cnt)
{
full += value / 2;
left += value % 2;
}
cout << 2 * full + (left + 1) / 2 << endl;
return 0;
}