Guest User

Untitled

a guest
Aug 7th, 2020
456
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  5. #define fr(i,k) for(i=0;i<k;i++)
  6. #define ALL(c) (c).begin(),(c).end()
  7. #define deb(x) cerr<<#x<<" = "<<x<<endl;
  8. #define SZ(x) (x).size();
  9. #define ll long long
  10. #define MOD 1000000007
  11. #define mp make_pair
  12. #define ff first
  13. #define ss second
  14. #define pb push_back
  15. #define em emplace_back
  16. #define ulli unsigned long long int
  17. #define INF 1e18
  18. typedef vector<int> vi;
  19. typedef vector<vi> vvi;
  20. typedef vector<bool> vb;
  21. typedef pair<int, int> ii;
  22. void solve();
  23.  
  24. void err(istream_iterator<string> it) {}
  25. template<typename T, typename... Args>
  26. void err(istream_iterator<string> it, T a, Args... args) {
  27. cerr << *it << " = " << a << endl;
  28. err(++it, args...);
  29. }
  30.  
  31. int main() {
  32. fastio;
  33. /*#ifndef ONLINE_JUDGE
  34. freopen("input.txt", "r", stdin);
  35. freopen("output.txt", "w", stdout);
  36. #endif*/
  37.  
  38. int t;
  39. //t=1;
  40. cin >> t;
  41.  
  42. while (t--)
  43. {
  44. solve();
  45. }
  46. return 0;
  47. }
  48.  
  49. bool Possible(map<int,int> &m,int f,int j,int mid)
  50. {
  51. ll c=0;
  52. for(auto k:m)
  53. {
  54. if(k.first==j)
  55. continue;
  56.  
  57. if(k.second>=f)
  58. mid--;
  59.  
  60. if(k.second<f)
  61. c+=k.second;
  62.  
  63. if(mid==0)
  64. return true;
  65.  
  66. }
  67.  
  68.  
  69. if(mid*1LL*f-c>0)
  70. return false;
  71.  
  72. return true;
  73. }
  74.  
  75. void solve()
  76. {
  77. int n,i,j,mx=INT_MIN,l,h,mid,ans=0;
  78. cin>>n;
  79.  
  80. int a[n];
  81. map<int,int> m;
  82.  
  83. for(i=0;i<n;i++)
  84. {
  85. cin>>a[i];
  86.  
  87. m[a[i]]++;
  88.  
  89. if(m[a[i]]>mx)
  90. {
  91. mx=m[a[i]];
  92. j=a[i];
  93. }
  94. }
  95.  
  96. l=0;
  97. h=n;
  98.  
  99. while(l<=h)
  100. {
  101. mid=l+(h-l)/2;
  102.  
  103. if(Possible(m,mx-1,j,mid))
  104. {
  105. ans=mid;
  106. l=mid+1;
  107. }
  108. else
  109. h=mid-1;
  110. }
  111.  
  112. cout<<ans<<endl;
  113.  
  114. }
  115.  
  116.  
  117.  
RAW Paste Data