Equalize the Array

The question

Input & Output

Simplify the question

We’re supposed to delete minimum number of elements to make the given array beautiful, which means every number in the array appears same times

Solve

First, we will save the array to a map. Since we will do a sort, which can’t be done with map, I created a vector of pair

ll a[maxn];
map<ll, int> mp;
vector<pair<int, int>> b;

bool cmp(pair<int, int> x, pair<int, int> y) {
    return x.second > y.second;
}

for (int i = 0; i < n; i++) {
    cin >> a[i];
    mp[a[i]]++;
}
for (auto it:mp) {
    b.emplace_back(it.first, it.second);
}
sort(b.begin(), b.end(), cmp);

The next step is the key. We sorted the vector with the number of elements in decreasing order.

$b[i].second*(i+1)$ means the number of elements will be left, so $n-b[i].second*(i+1)$ will be the number of elements we will delete(for this one).

Then we just find the minimum one and output

int ans = inf;
for (int i = 0; i < b.size(); i++) {
    ans = min(ans, n - b[i].second * (i + 1));
}

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
const int inf = INT_MAX;
const int mod = 1e9 + 7;

typedef long long ll;

ll a[maxn];
map<ll, int> mp;
vector<pair<int, int>> b;

bool cmp(pair<int, int> x, pair<int, int> y) {
    return x.second > y.second;
}

void solve() {
    int n;
    cin >> n;
    b.clear();
    mp.clear();
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    for (auto it:mp) {
        b.emplace_back(it.first, it.second);
    }
    sort(b.begin(), b.end(), cmp);
    int ans = inf;
    for (int i = 0; i < b.size(); i++) {
        ans = min(ans, n - b[i].second * (i + 1));
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Adam's blog