Competitive Programming Solutions

1478A - Nezzar And Colorful Balls

28 Jan 2021 — Tags: greedy — URL

Note that each subarray of equal value has to be painted with $x$ colors, where $x$ is the size of such subarray. This is because otherwise, this would yield a color sequence that is not strictly increasing.

To find the minimum number of colors needed, we need to find the biggest subarray of equal value.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi freq(n + 1, 0);
        for (int i = 0; i < n; ++i)
        {
            int ai;
            cin >> ai;
            freq[ai]++;
        }
        cout << *max_element(begin(freq), end(freq)) << endl;
    }
    return 0;
}

Related posts