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
#include <stdio.h>
#include <stdlib.h>

int compare( const int *a, const int *b )
{
    if(*a > *b) return -1;   
    if(*a < *b) return 1;
    return 0;
}

int main()
{
int n,N,tmp,*A,*H,sH,iL,sT;

	scanf("%d",&N);
	A = (int*) malloc(N*sizeof(int));
	H = (int*) malloc((N+1)*sizeof(int));
	for (n = 0; n < N; n++)
	{
		scanf("%d",&tmp);
		A[n] = tmp;
		H[n] = 0;
	}
	H[n] = 0;
	for (n = 0; n < N; n++)
	{
		H[A[n]]++;
	}
	qsort(H,N+1,sizeof(int),( int(*)(const void *,const void *) ) compare);
	
	sH = 0;
	for (n = 0; n < N; n++)
	{
		sH += H[n];
//		printf("%d ",H[n]);
	}		
//	printf("\nsH = %d\n",sH);
	
	iL = 0;
	sT = 0;
	while (sT < sH)
	{
		sT += 2*H[iL]-1;
		iL++;
	}
//	printf("iL = %d, sT = %d\n",iL,sT);
	printf("%d\n",iL);
	
	free(A);
	free(H);
	
	return 0;
}