Hiểu bài toán

Bài toán yêu cầu tìm số lượng giày tối thiểu Apok phải đổi trả về nhà máy. Ban đầu có N đôi giày, mỗi đôi gồm một chiếc giày trái (li) và một chiếc giày phải (ri). Tuy nhiên, giày trong kho bị lẫn lộn, Apok cần tạo ra N đôi giày hoàn chỉnh (mỗi đôi 1 trái, 1 phải) sao cho số lượng giày phải đổi là ít nhất. Giày chỉ có thể dùng được khi kích thước của giày trái và giày phải bằng nhau. Ta cần chọn ra các cặp (trái, phải) cùng kích thước để dùng, số giày còn lại không tạo thành đôi được sẽ phải đổi. Nói cách khác, ta cần tìm số lượng giày không thể tham gia vào bất kỳ cặp cùng kích thước nào.

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

Cách Hash Map (Đếm tần suất)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    map<int, int> cntL, cntR;

    for(int i = 0; i < N; i++) {
        int x; cin >> x;
        cntL[x]++;
    }
    for(int i = 0; i < N; i++) {
        int x; cin >> x;
        cntR[x]++;
    }

    long long paired = 0;
    // Duyệt qua từng kích thước có trong kho giày trái
    for(auto &p : cntL) {
        int size = p.first;
        // Số lượng giày có thể ghép đôi cùng kích thước là số lượng ít hơn
        // giữa giày trái và giày phải của kích thước đó
        paired += min(cntL[size], cntR[size]);
    }

    // Số giày phải đổi = Tổng số giày ban đầu - 2 * số lượng giày đã ghép được
    // (vì mỗi cặp thành công lấy đi 2 chiếc)
    long long result = 2LL * N - 2 * paired;
    cout << result;
    return 0;
}

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

Cách tiếp cận này dựa trên quan sát: Với mỗi kích thước x, số lượng cặp giày (trái, phải) cùng kích thước x tối đa có thể tạo được là min(số lượng giày trái kích thước x, số lượng giày phải kích thước x). Ta dùng hai map (hoặc unordered_map) để đếm tần suất xuất hiện của từng kích thước cho giày trái và giày phải. Sau đó, duyệt qua các kích thước có trong map giày trái, lấy số lượng ghép đôi được cộng vào biến paired. Kết quả cuối cùng là tổng số giày ban đầu (2N) trừ đi 2 lần số giày đã ghép được (vì mỗi cặp dùng 2 chiếc). Ví dụ: có 3 giày trái size 1, 2 giày phải size 1 thì được 2 cặp, tương đương 4 chiếc giày được giữ lại.

Cách Hash Map (Tính chênh lệch)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    unordered_map<long long, long long> cntL, cntR;

    for (int i = 0; i < N; ++i) {
        long long x; cin >> x;
        cntL[x]++;
    }
    for (int i = 0; i < N; ++i) {
        long long x; cin >> x;
        cntR[x]++;
    }

    long long ans = 0;
    // Tính chênh lệch cho các kích thước có ở bên trái
    for (auto &p : cntL) {
        long long size = p.first;
        long long l = p.second;
        long long r = cntR[size]; // mặc định là 0 nếu không t tồn tại
        ans += abs(l - r);
        cntR.erase(size); // Xóa để không xử lý lại
    }
    // Xử lý các kích thước chỉ có ở bên phải (còn lại trong cntR)
    for (auto &p : cntR) {
        ans += p.second;
    }

    cout << ans;
    return 0;
}

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

Cách này tối ưu hơn về mặt thời gian bằng cách sử dụng unordered_map. Logic tính toán khác một chút nhưng cùng bản chất. Với mỗi kích thước x:

• Nếu có a giày trái và b giày phải, ta giữ được min(a, b) cặp. Số lượng giày dư ra (phải đổi) là |a - b|.
• ans += abs(a - b)
• Với những kích thước chỉ có ở một phía (ví dụ chỉ có giày trái nhưng không có giày phải), số lượng giày dư chính là tần suất của chúng.
• Công thức tổng quát: Tổng số giày phải đổi = Tổng(abs(cntL[x] - cntR[x])) cho mọi kích thước x. Cách này cũng xử lý được các kích thước chỉ xuất hiện ở một phía.

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

Bài học kinh nghiệm

• Bài toán quy về đếm tần suất kích thước giày trái và giày phải.
• Với mỗi kích thước, số lượng giày tối đa giữ lại là số lượng ít hơn giữa giày trái và giày phải của kích thước đó.
• Số giày phải đổi = Tổng số giày - 2 * (số lượng giày đã ghép được).

Lỗi thường gặp

• Xử lý sai với các kích thước chỉ xuất hiện ở một bên (ví dụ chỉ có giày trái size 10 nhưng không có giày phải size 10).
• Sử dụng int cho biến lưu kết quả hoặc tần suất có thể gây tràn số (Overflow) nếu N lớn.