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
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int cnt[MAXN];
int n;
int main()
{
   cin>>n;
   for(int i=0; i<n; i++)
   {
       int x;
       cin>>x;
       cnt[x]++;
   }
   sort(cnt+1, cnt+n+1, greater<int>());
   /*for(int i=1; i<=n; i++)
   {
       cout<<cnt[i];
   }*/
   int r=n;
   int segmentcount=0;
   for(int l=1; l<=r; l++)
   {
       while(cnt[l]>cnt[r])
       {
           cnt[l]-=cnt[r];
           cnt[r]=0;
           r--;
       }
       cnt[r]-=(cnt[l]-1);
       //cnt[l]=0;
       segmentcount++;
   }
    cout<<segmentcount;
    return 0;
}