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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <algorithm>
#include <vector>
#define DEBUG false
using namespace std;
vector<int> ciag, lider;
struct Lid{
    int a;
    int ile;
}lid[500000];
int n,x,nLid=0;
int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d",&x);
        ciag.push_back(x);
    }
    ciag.push_back(0);
    sort(ciag.begin(),ciag.begin()+n);

    for(int i = 0; i < n; i++){
        x = 1;
        while( (i < n-1) && (ciag[i] == ciag[i+1]) ) {
            x++;
            i++;
        }
        lider.push_back(x);
        nLid++;
    }
    sort(lider.begin(),lider.end());
    int last = lider[0];
    int counter = 0;
    int al = 0;
    for(int i=0; i<nLid; i++){
        if(last == lider[i])
            counter++;
        else{
            lid[al].a = last;
            lid[al].ile = counter;
            counter = 1;
            al++;
            last = lider[i];
        }
        if(DEBUG)printf("%d ",lider[i]);
    }
    lid[al].a = last;
    lid[al++].ile = counter;
    if(DEBUG)printf("\n");
    if(DEBUG)for(int i=0; i<al; i++){
        printf("%d - %d\n",lid[i].a,lid[i].ile);
    }

    int a,p=0;
    int suma = 0;
    for(a = al-1; a>p; ){
        if( lid[a].ile * (lid[a].a-1) <= lid[p].ile * lid[p].a){
           lid[p].ile -= lid[a].ile * (lid[a].a-1);
           suma += lid[a].ile;
           a--;
           if(DEBUG)printf("suma:%d lidp:%d\n",suma,lid[p].ile);
        } else {
            suma += lid[p].ile * lid[p].a;
            lid[a].ile -= lid[p].ile * (lid[a].a-1);
            p++;
            if(DEBUG)printf("pyk:%d suma:%d %d\n",p,suma,lid[a].ile);
        }
    }
    int rest = lid[a].ile * lid[a].a;
    int sub = lid[a].a + (lid[a].a-1);
    while(rest >= sub ){
        rest -= sub;
        suma ++;
    }
    if(rest>0)
        suma++;
    printf("%d\n",suma);
    return 0;
}