Hiểu bài toán

Bài toán yêu cầu xử lý hai mảng A và B. Mảng A có n phần tử, mảng B có m phần tử.

• Bước 1: Loại bỏ khỏi mảng A tất cả các phần tử có giá trị xuất hiện trong mảng B.
• Bước 2: Từ các phần tử còn lại của mảng A, tính giá trị lớn nhất của 'giá trị phần tử * số lần xuất hiện của nó'.
• Bước 3: In ra các phần tử còn lại của mảng A (theo thứ tự xuất hiện ban đầu) và giá trị lớn nhất tính được ở Bước 2. Nếu không có phần tử nào sót lại, in ra 0.

Các cách tiếp cận

Cách Quản lý trạng thái bằng Hash Map

#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    ifstream in("thuong.inp");
    ofstream out("thuong.out");
    int n, m;
    in >> n >> m;
    vector<long long> vt(n);
    unordered_map<long long, vector<int>> mp;
    for (int i = 0; i < n; i++) {
        in >> vt[i];
        mp[vt[i]].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        long long tmp;
        in >> tmp;
        if (mp[tmp].size() == 0) {
            continue;
        }
        mp[tmp].clear();
    }
    long long max = 0;
    vector<int> index;
    bool check = false;
    for (auto x : mp) {
        if ((x.second).size() == 0) {
            continue;
        }
        else {
            check = true;
            long long tmp = x.first * (x.second).size();
            if (tmp > max) {
                max = tmp;
            }
            for (auto i : (x.second)) {
                index.push_back(i);
            }
        }
    }
    if (!check) {
        out << 0;
        return 0;
    }
    sort(index.begin(), index.end());
    for (auto i : index) {
        out << vt[i] << " ";
    }
    out << endl;
    out << max;
    in.close();
    out.close();
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Cách tiếp cận này sử dụng một Hash Map (unordered_map) để lưu trữ các chỉ số của từng giá trị trong mảng A.

1. Đọc dữ liệu: Đọc mảng A và lưu chỉ số của từng giá trị vào map (ví dụ: mp[5] = {0, 2} nghĩa là giá trị 5 nằm ở chỉ số 0 và 2).
2. Loại bỏ: Khi đọc các giá trị từ mảng B, ta xóa hết các chỉ số trong map tương ứng với giá trị đó (mp[tmp].clear()).
3. Tính toán và thu thập: Duyệt qua map, nếu một giá trị còn chỉ số (tức chưa bị loại bỏ), ta tính giá trị * số lượng và cập nhật max. Đồng thời, thêm tất cả chỉ số của giá trị đó vào một mảng phụ.
4. Xuất kết quả: Sắp xếp mảng chỉ số phụ để in ra các giá trị theo đúng thứ tự xuất hiện ban đầu trong mảng A.

Độ phức tạp: Với N phần tử, việc xây dựng map là O(N). Việc duyệt map và thêm vào mảng chỉ số là O(N). Việc sắp xếp mảng chỉ số là O(N log N). Tổng thể là O(N log N). Không gian là O(N).

Cách Hash Map Đếm tần suất và Lọc

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define TranHungss(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

signed main(){
    TranHungss();
    ifstream cin("THUONG.INP");
    ofstream cout("THUONG.OUT");
    int n, m;
    cin >> n >> m;
    int a[n], b[m];
    unordered_map<int,int> mp;
    for(auto &x : a){
        cin >> x;
        ++mp[x];
    }
    for(auto &x : b){
        cin >> x;
        mp[x] = 0;
    }
    int res = 0;
    for(auto it : mp){
        res = max(res, it.first * it.second);
    }
    if(res == 0){
        cout << res << endl;
    }
    else{
        for(auto x : a){
            if(mp[x] != 0){
                cout << x << " ";
            }
        }
        cout << endl;
        cout << res << endl;
    }
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này sử dụng Hash Map để đếm tần suất xuất hiện của các phần tử trong mảng A.

1. Đọc mảng A và đếm tần suất vào map (mp[x]++).
2. Đọc mảng B và gán tần suất của các giá trị này về 0 trong map (mp[x] = 0).
3. Tính giá trị lớn nhất: Duyệt qua map, nếu tần suất > 0 thì cập nhật max = max(max, value * count).
4. In các phần tử còn lại: Duyệt lại mảng A ban đầu, kiểm tra xem tần suất trong map có khác 0 không. Nếu khác 0 thì in ra.

Độ phức tạp: O(N) vì ta chỉ duyệt qua các mảng một vài lần và thao tác với Hash Map là O(1) trung bình.

Cách Sử dụng Set để Loại trừ

#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    ifstream fi("thuong.inp");
    ofstream fo("thuong.out");

    int n, m;
    fi >> n >> m;

    vector<int> a(n);
    unordered_set<int> b;
    unordered_map<int, int> dict1;

    for (int i = 0; i < n; i++) {
        fi >> a[i];
    }

    for (int i = 0, x; i < m; i++) {
        fi >> x;
        b.insert(x);
    }

    for (int pt : a) {
        if (b.find(pt) == b.end()) {
            fo << pt << " ";
            dict1[pt]++;
        }
    }

    fo << "\n";

    long long max1 = 0;
    for (const auto &[k, v] : dict1) {
        max1 = max(max1, 1LL * k * v);
    }

    fo << max1 << "\n";

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này chia việc xử lý thành hai giai đoạn rõ ràng:

1. Lọc và In: Đọc mảng B vào một unordered_set để tra cứu nhanh. Trong khi đọc mảng A, nếu phần tử không có trong Set B, ta in nó ra ngay lập tức và đồng thời đếm tần suất vào map dict1.
2. Tính Max: Sau khi đã in xong các phần tử và có đầy đủ tần suất, ta chỉ cần duyệt qua dict1 để tìm max.

Độ phức tạp: O(N) do các thao tác đều là truy cập thường (constant time).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia thành 2 việc chính: (1) Lọc dữ liệu theo danh sách loại trừ, (2) Thống kê và tìm max.
• Hash Map (Dictionary) là cấu trúc dữ liệu tối ưu nhất để đếm tần suất và tính toán giá trị lớn nhất.

Lỗi thường gặp

• Tràn số nguyên (Integer Overflow): Kết quả giá trị * số lượng có thể rất lớn, luôn dùng kiểu long long.
• Thứ tự in ra: Yêu cầu in ra các phần tử còn lại theo thứ tự xuất hiện ban đầu của chúng trong mảng A, không phải in theo thứ tự từ điển.