\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Mục tiêu:

Bước 1: Xóa \(k\) phần tử sao cho tối ưu được số lượng phần tử khác nhau trong dãy là nhiều nhất

Bước 2: Tìm số lượng phần tử khác nhau trong dãy sau khi xóa

• A) Xóa k phần tử

Trâu: Thử chọn \(k\) số để xóa trong \(n\) số. Số cách chọn hay độ phức tạp thồi gian là \(O(C^k_n)\)

Random: Thử chọn ngẫu nhiên \(k\) số trong \(t\) lần. Xác xuất đúng là thấp hơn \(O(\frac{t}{C^k_n})\)

Tham lam: Vì khi loại một phần trong các số trùng nhau (không loại hết) sẽ không ảnh hưởng tới số lượng số khác nhau. Nên ta sẽ ưu tiên loại các phần trùng này trước. Code tối ưu sẽ đạt được \(O(n)\)

Nhánh cận: Xóa \(k\) số \(\Leftrightarrow\) chọn \(n - k\) số còn lại. Dùng các nhận xét để loại bỏ các nhánh ko cần thiết mà phải kiểm tra ít dãy hơn. Nếu code tối ưu bằng nhận xét tham lam sẽ là \(O(n)\), còn không sẽ là \(O(C^k_n)\)

Quy hoạch động: Nếu cài bằng tham lam có thể đạt được \(O(n + k)\). Nếu code bằng nhánh cận thêm nhớ thì \(O(n \times k)\)

• 😎 Đếm số phần tử khác nhau

Mỗi lần xóa \(k\) số. Cho \(n - k\) số còn lại vào một mảng mới mới, sắp xếp và đếm sẽ mất \(O(n log n)\) thời gian mỗi lần chọn

Mỗi lần xóa \(k\) số. Cho \(n - k\) số còn lại vào mảng đánh dấu và đếm. Cách này mất \(O(max(a_i) - min(a_i))\) thời gian mỗi lần chọn

Mỗi lần xóa từng số \(x\). Nếu \(x\) có trong mảng đánh dấu thì tăng số lượng số khác nhau, ngược lại đánh dấu \(x\) tồn tại trong mảng. Cách này mất \(O(max(a_i) - min(a_i))\) thời gian một cách độc lập với việc chọn

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Cách 1: Tham lam trực tiếp trên mảng tần số (offline)

Gọi \(c[x]\) là số lần xuất hiện của \(x\) trong mảng

Ta loại các phần tử trùng nhau: Duyệt qua các giá trị lớn hơn 1, giảm \(k\) và \(c[x]\) đi \(min(k, c[x])\) phần tử

Nếu \(k > 0\), ta phải xóa các phần tử khác: Duyệt qua các giá trị bằng 1, giảm \(k\) và \(c[x]\) đi \(1\) phần tử

Duyệt qua các giá trị, đếm số lượng vị trí \(x\) có \(c[x] \geq 1\), hay số lượng phần tử khác nhau còn lại

• Cách 2: Tham lam trực tiếp trên mảng đánh dấu (online)

Ta đã có nhận xét: Xóa một phần trong các phần tử trùng nhau với một số \(x\) nào đó (không xóa hết) sẽ không giảm số lượng phần tử phân biệt

Ta có thể nhận xét chặt hơn: Tách mảng thành 2 phần, lấy trước một phần đầu gồm các phần tử phân biệt, và phần sau gồm các phần tử có giá trị trùng với một phần tử nào đó trong phần đầu. Lúc này ta xóa bất cứ phần tử nào trong phần sau cũng không làm giảm số lượng phần tử phân biệt có trong phần đầu.

Vậy ta chỉ cần quan tâm 2 dữ liệu là có thể cho ra kết quả với mọi truy vấn \(k\): \(diff\) là tổng số phần tử trong phần đầu (số phần tử phân biệt). \(same\) là tổng số phần tử phần sau (số phần tử mà đã có giá trị tồn tại ở phần đầu)

Vậy ta chỉ cần dùng mảng đánh dấu. Mỗi lần duyệt qua một số \(x\). Nếu \(x\) chưa tồn tại trong mảng đánh dấu, đánh dấu nó và cho vào phần đầu, tăng số lượng phần tử phân biệt. Ngược lại nếu \(x\) đã tồn tại, tăng số lượng phần tử trùng.

Với truy vấn \(k\) bất kì. Ta ưu tiên xóa các phần tử trùng trước, số lượng cần xóa là \(min(k, same)\), số lượng còn lại là \(k - min(k, same)\). Sau đó ta xóa thêm các phần tử phân biệt, số lượng cần xóa là \(k - min(k, same)\), số phần tử phân biệt còn lại là \(diff - (k - min(k, same))\)

\(\color{green}{\text{Code tham khảo }}\): Tham lam

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cstring>

using namespace std;

int query()
{
    int n;
    cin >> n;

    int cnt[n + 1];
    memset(cnt, 0, sizeof(cnt));

    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;

        ++cnt[x];
    }

    int k;
    cin >> k;

    for (int x = 1; x <= n; ++x)
    {
        if (cnt[x] > 1)
        {
            k -= cnt[x] - 1;
            cnt[x] = 1;
        }
    }

    for (int x = 1; x <= n; ++x)
    {
        if (k > 0 && cnt[x] == 1)
        {
            k -= 1;
            cnt[x] = 0;
        }
    }

    int res = 0;
    for (int x = 1; x <= n; ++x)
    {
        if (cnt[x] > 0)
        {
            res += 1;
        }
    }

    cout << res << '\n';
    return 0;
}

int main()
{
    int q;
    cin >> q;

    while (q-->0)
    {
        query();

    }


    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Giải trực tiếp, Tham lam

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cstring>

using namespace std;

int query()
{
    int n;
    cin >> n;

    bool exist[n + 1];
    memset(exist, false, sizeof(exist));

    int same = 0, diff = 0;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;

        if (exist[x] == false)
        {
            exist[x] = true;
            ++diff;
        }
        else
        {
            ++same;
        }
    }

    int k;
    cin >> k;

    int res = diff - (k - min(k, same));
    cout << res << '\n';
    return 0;
}

int main()
{
    int q;
    cin >> q;

    while (q-->0)
    {
        query();

    }


    return 0;
}