CF1393C Pinkie Pie Eats Patty-cakes

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100001;
 4 int cnt[N], a[N], n;
 5 bool check(int x)
 6 {
 7     set<pair<int, int>, greater<pair<int, int>>> st; 
 8     for (int i = 1; i <= n; i++) cnt[i] = 0;
 9     for (int i = 0; i < n; i++) cnt[a[i]]++;
10     for (int i = 1; i <= n; i++)
11     {
12         if (cnt[i]) st.insert(make_pair(cnt[i], i));
13     } 
14     vector<int> v;
15     for (int i = 0; i < n; i++)
16     {
17         if (i >= x + 1)
18         {
19             int j = v[i - x - 1];
20             if (cnt[j] > 0) st.insert(make_pair(cnt[j], j));
21         }
22         if (st.empty()) return false;
23         auto it = st.begin();
24         v.push_back(it->second);
25         assert(cnt[it->second] > 0);
26         cnt[it->second]--;
27         st.erase(it);
28     }
29     return true;
30 }
31 int main()
32 {
33     int T; cin >> T;
34     while (T--)
35     {
36         cin >> n;
37         for (int i = 0; i < n; i++) cin >> a[i];
38         int l = 0, r = n - 2, res = 0;
39         while (l <= r)
40         {
41             int m = l + r >> 1;
42             if (check(m))
43             {
44                 res = m;
45                 l = m + 1;
46             }
47             else r = m - 1;
48         }
49         cout << res << endl;
50     }
51     return 0;
52 }