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

int N;
int tab[500000];
long long int z=0;
int x1=0;
int x2=0;
int m=0;
int n=0;


int compare(const void * a, const void * b)
{
 return *(int*)b - *(int*)a;
}

int main(){

int x;
scanf ("%d",&N);

for(int i=0;i<N;i++)
{
  scanf("%d",&x);
  tab[x-1]++;
}

qsort(tab, N, sizeof(int), compare);

x2=N-1;
while(x1<=x2)
{
  n++;
  m=tab[x1]-1;
  z+=m;
  tab[x1]=0;
  x1++;
  while(z>=tab[x2] && x2>=x1)
  {
    z-=tab[x2];
    tab[x2]=0;
    x2--;
  }
  tab[x2]-=z;
  z=0;
}

printf("%d\n",n);
return 0;
}