1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <map>
#include <vector>
#include <algorithm> 

using namespace std;
int main()
{
	int tests = 0;
	cin >> tests;

	map<int, int> countOfSpecificNumber;
	
	for (int i = 0; i < tests; ++i)
	{
		auto number = 0;
		cin >> number;

		countOfSpecificNumber[number]++;
	}

	vector<int> vectorCountOfSpecificNumber;

	for (auto& n : countOfSpecificNumber)
	{
		vectorCountOfSpecificNumber.push_back(n.second);
	}

	sort(vectorCountOfSpecificNumber.begin(), vectorCountOfSpecificNumber.end(), greater<int>());

	//for (auto& n : vectorCountOfSpecificNumber)
	//{
	//	cout << n << endl;
	//}

	auto result = 0;
	auto begin = 0;
	auto end = vectorCountOfSpecificNumber.size() - 1;
	while (vectorCountOfSpecificNumber[begin] != vectorCountOfSpecificNumber[end])
	{
		if (vectorCountOfSpecificNumber[begin] - vectorCountOfSpecificNumber[end] >= vectorCountOfSpecificNumber[begin + 1])
		{
			vectorCountOfSpecificNumber[begin] -= vectorCountOfSpecificNumber[end];
			result++;
			begin++;
			end--;
		}
		if (vectorCountOfSpecificNumber[begin] - vectorCountOfSpecificNumber[end] < vectorCountOfSpecificNumber[begin + 1])
		{
			vectorCountOfSpecificNumber[begin] -= vectorCountOfSpecificNumber[end];
			result++;
			begin++;
			end--;
		}
	}

	cout << result + (end - begin + 1);
}