Balloons (Editorial)

Помітимо, що якщо ми хочемо отримати набір кульок одного кольору, то найвигідніше зробити всі кульки того кольору, який вже трапляється найчастіше. Оскільки, якщо ми виберемо будь-який інший колір, то кількість перефарбувань буде більшою, адже доведеться перефарбувати навіть ті кульки, що вже мають найпоширеніший колір.

Тому задача повністю зводиться до знаходження максимальної частоти якогось кольору.

Нехай $mx$ — максимальна кількість кульок одного й того ж кольору. Тоді мінімальна кількість кульок, які потрібно перефарбувати: $n$−$mx$

Оскільки кольори задані числами від 1 до 9, їхню кількість можна дуже швидко порахувати за допомогою масиву лічильників.

Асимптотика рішення $O$ $($$n$$)$.

#include <bits/stdc++.h>

using namespace std;

#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define ll long long
#define ld long double
#define pll pair <ll, ll>

const ll DIM = 5e5+7;
const ll INF = 1e18+7;
const ll mod = 1e9+7;

ll c[12];
ll n, k;

int main(){

    cin>>n;

    ll mx = 0;
    for(int i=1; i<=n; i++){
        
        cin>>k;
        c[k]++;

        if(c[k] > mx) mx = c[k];
    }
    
    cout<<n-mx<<endl;

    return 0;
}