10 complete half of the questions

This problem needs to use t Knowledge of hash tables , First, the hash table is a hash table Also known as hash table   He and adjacency table are not the same thing But they are all done in the form of tables . Don't confuse them .

Then let's take a look at what a hash table is Students who didn't attend online classes before Now listen Take you to quickly understand Hashtable （ Hash table ） How it works _ Bili, Bili _bilibili

10  Complete half of the topic

author : Turbo The time limit : 1S chapter :  curriculum design

Problem description :

Yes N A friend participated in the 「 To make friends 」 Offline activities . The sponsor provided 2*N questions , integer array questions Each number corresponds to the type of knowledge points involved in each topic .

If each friend chooses a different question , Please return to the selected N How many types of knowledge points does the topic contain at least .

Example 1：

Input ：

4

2 1 6 2

Output ：1

explain ： share 2 Wei Keyou , stay 4 Choose from the questions 2 topic .

The type of knowledge points can be selected as 2 I'm not sure , At this time, there is only one knowledge point type , So at least 1 There are three types of knowledge points .

Example 2：

Input ：

12

1 5 1 3 4 5 2 5 3 3 8 6

Output ：2

explain ： share 6 Wei Keyou , stay 12 Choose a topic from the following questions , Need to choose 6 topic .

3 The type of knowledge points for bit selection completion is 3 The subject of ,3 The type of knowledge points for bit selection completion is 5 The subject of , So at least 2 There are three types of knowledge points .

Enter description :

Enter two lines ：

The first line is an integer n Representative array questions The length of ,n=2*N,N Is the number of friends .

Second line input n An integer represents an array questions The elements of .

Tips ：

    2 <= n <= 10^5

    1 <= questions[i] <= 1000

Output an integer to represent the result .

Input example :

6
1 2 3 4 5 1

The output shows that :

2

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x, int y)
{
	return x > y;
}
int main()
{
	int arr[100001] = { 0 };
	int haxi[100001] = { 0 };
	int n = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		haxi[arr[i]]++;
	}
	int people = n / 2;
	sort(haxi, haxi+1000,cmp);
	int total = 0;
	for (int i = 0; i < 1000; i++)
	{
		if (people > 0)
		{
			people -= haxi[i];
			total++;
		}
		else
		{
			break;
		}

	}
	cout << total << endl;
	return 0;
}