fork download
copy 
  1. /*
  2. -> Don't stop when you're tired, stop when you're done.
  3. -> From the river to the sea, Palestine will be free.
  4. --> @author: MIDORIYA_
  5. */
  6. //*==============================================================
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. typedef long long ll;
  10. typedef double db;
  11. typedef long double ld;
  12. typedef pair<int, int> pii;
  13. typedef pair<ll, ll> pll;
  14. typedef vector<int> vi;
  15. typedef vector<ll> vll;
  16. typedef vector<db> vd;
  17. typedef vector<ld> vld;
  18. typedef vector<bool> vb;
  19. typedef vector<vector<ll>> vvl;
  20. typedef vector<vector<int>> vvi;
  21. typedef vector<pii> vii;
  22. typedef set<int> si;
  23. typedef set<ll> sl;
  24. typedef multiset<int> msi;
  25. typedef multiset<ll> msl;
  26. #define pb push_back
  27. #define pf push_front
  28. #define popb pop_back
  29. #define popf pop_front
  30. #define fi first
  31. #define se second
  32. #define all(x) x.begin(), x.end()
  33. #define rall(x) x.rbegin(), x.rend()
  34. #define endl "\n"
  35. const int MOD = 998244353, mod = 1e9 + 7, maxA = 1e5 + 5;
  36. #define time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs";
  37. //*===================>>>FastIO - FileIO<<<=========
  38. void fastIO()
  39. {
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.     cout.tie(nullptr);
  43. }
  44. void fileIO()
  45. {
  46. #ifndef ONLINE_JUDGE
  47.     freopen("in.txt", "r", stdin);
  48.     freopen("out.txt", "w", stdout);
  49. #endif
  50. }
  51. //*===================>>>ONE-FOR-ALL<<<=============
  52. void OneForAll()
  53. {
  54.     int n;
  55.     cin >> n;
  56.     map<int, int> mp;
  57.     for (int i = 0; i < n; i++)
  58.     {
  59.         int x;
  60.         cin >> x;
  61.         mp[x]++;
  62.     }
  63.  
  64.     map<int, int> cnt;
  65.     for(auto &[x, y] : mp)
  66.     {
  67.         cnt[y]++;
  68.     }
  69.  
  70.     int ans = n;
  71.     int after = mp.size(), before = 0, sum = n;
  72.     for(auto [x, y] : cnt)
  73.     {
  74.         sum -= x * y;
  75.         after -= y;
  76.         ans = min(ans, before + (sum - x * after));
  77.         before += x * y;
  78.     }
  79.  
  80.     cout << ans << endl;
  81. }
  82.  
  83. int main()
  84. {
  85.     fastIO();
  86.     // fileIO();
  87.  
  88.     ll tc = 1, t = 1;
  89.     cin >> t;
  90.     while (t--)
  91.     {
  92.         // cout << "Case " << tc++ << ": ";
  93.         OneForAll();
  94.     }
  95.     time;
  96.     return 0;
  97. }
Success #stdin #stdout #stderr 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time Taken: 0.005997 Secs
https://ideone.com/AHkcVF
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!