思路：
二分+贪心。
实现：
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 }