Hiểu bài toán

Bài toán yêu cầu tính số lượng đôi tất có thể ghép được từ n chiếc tất cho trước. Hai chiếc tất có thể ghép đôi nếu chúng có cùng màu. Với mỗi màu sắc xuất hiện, số đôi tất có thể tạo ra từ màu đó bằng số lượng chiếc tất của màu đó chia lấy nguyên cho 2. Tổng số đôi tất là tổng số đôi tất của tất cả các màu.

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

Cách Sử dụng mảng đếm (Fixed-size Array)

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

int main() {
    int N;
    cin >> N;
    vector<int> cnt(101, 0);

    for (int i = 0; i < N; i++) {
        int c;
        cin >> c;
        if (c >= 1 && c <= 100) {
            cnt[c]++;
        }
    }

    int pairs = 0;
    for (int color = 1; color <= 100; color++) {
        pairs += cnt[color] / 2;
    }

    cout << pairs;
    return 0;
}

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

Phương pháp này sử dụng một mảng cố định kích thước 101 (vì màu sắc nằm trong khoảng 1-100) để lưu số lượng tất của mỗi màu. Chúng ta đọc từng chiếc tất và tăng giá trị tương ứng trong mảng lên 1. Sau đó, duyệt qua mảng để tính tổng số đôi tất bằng cách lấy số lượng mỗi màu chia cho 2.

Ưu điểm:

• Đơn giản, dễ hiểu.
• Truy cập và cập nhật dữ liệu nhanh chóng O(1).
• Tiêu tốn bộ nhớ cực kỳ ít.

Nhược điểm:

• Chỉ hoạt động tốt khi giới hạn màu sắc nhỏ và cố định (như bài toán này). Nếu màu sắc lên tới 10^9, mảng không thể khai báo.

Cách Sử dụng map (Hash Map)

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

int main(){
    int n;
    cin >> n;
    map<int,int> mp;

    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        mp[x]++;
    }

    int dem = 0;
    for(auto x : mp){
        dem += x.second / 2;
    }

    cout << dem;
}

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

Phương pháp này sử dụng cấu trúc dữ liệu Map (hoặc Hash Map) để lưu số lượng tất theo từng màu sắc động.

• Mỗi khi đọc một màu sắc, ta cập nhật số lượng vào map.
• Cuối cùng, duyệt qua các cặp (key, value) trong map để tính tổng số đôi.

Ưu điểm:

• Linh hoạt, hoạt động tốt ngay cả khi màu sắc nằm trong khoảng giá trị lớn (ví dụ lên tới 10^9).
• Không cần quan tâm trước giới hạn của màu sắc.

Nhược điểm:

• Tốn bộ nhớ hơn mảng cố định.
• Tốc độ truy cập và cập nhật chậm hơn mảng (O(log K) thay vì O(1)).

Cách Sử dụng mảng đếm với Map (C++ Map)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    map<int, int> mp;
    int n; cin>>n;
    for(int i=0; i<n; i++){
        int x; cin>>x;
        mp[x]++;
    }
    int cnt=0;
    for(auto x: mp){
        if(x.second>1){
            cnt+= (x.second/2);
        }
    }
    cout<<cnt;
}

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

Đây là cách tiếp cận tương tự như cách trên nhưng được trình bày chi tiết hơn một chút trong vòng lặp tính toán. Logic hoàn toàn giống nhau: đếm tần suất màu sắc bằng map rồi tính tổng số đôi.

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

Bài học kinh nghiệm

• Bài toán về cơ bản là bài toán đếm tần suất (Frequency Counting).
• Số đôi tất tạo được từ một màu sắc là tổng của các cặp 2 chiếc tất, tương đương với phép chia lấy nguyên (integer division) số lượng tất của màu đó cho 2.

Lỗi thường gặp

• Quên xử lý trường hợp input có số lượng lớn (nên dùng fast I/O như ios::syncwithstdio(false) và cin.tie(0)).
• Nếu dùng mảng tĩnh, cần đảm bảo kích thước mảng đủ lớn để chứa giá trị lớn nhất của c_i (ở đây là 100, nhưng khai báo 101 cho an toàn).
• Nếu dùng map, lặp qua map và xóa phần tử ngay trong vòng lặp có thể gây lỗi logic hoặc runtime error (dù trong bài này không cần xóa).