Hiểu bài toán

Bài toán yêu cầu tìm số nguyên dương $x$ xuất hiện nhiều nhất trong tập hợp các giá trị $|ai - bi|$ (chênh lệch tuyệt đối giữa hai số nguyên $ai$ và $bi$ được nhập vào cho $n$ cặp số). Nếu có nhiều số xuất hiện cùng số lần, ta cần in ra số đó. Dữ liệu đầu vào gồm số nguyên $n$ và $n$ cặp số nguyên $(ai, bi)$.

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

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

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

int main() {
    freopen("chenhlech.INP", "r", stdin);
    freopen("chenhlech.OUT", "w", stdout);

    int n;
    cin >> n;
    map<int, int> mp;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        int diff = abs(a - b);
        mp[diff]++;
    }

    int max_freq = 0;
    int best_val = 0;

    // Duyệt qua các cặp (key, value) trong map
    for (const auto& x : mp) {
        if (x.second > max_freq) {
            max_freq = x.second;
            best_val = x.first;
        }
    }

    cout << best_val << endl;
    return 0;
}

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

Phương pháp này sử dụng một map (hoặc unordered_map) để đếm tần suất xuất hiện của mỗi giá trị chênh lệch. Với mỗi cặp số đầu vào, ta tính giá trị chênh lệch tuyệt đối và cập nhật vào map. Sau đó, ta duyệt qua map để tìm giá trị có số lần xuất hiện lớn nhất. Do map ở C++ thường được cài đặt bằng cây đỏ-đen nên độ phức tạp cho mỗi thao tác chèn và tìm kiếm là O(log n), dẫn đến tổng độ phức tạp O(n log n).

Cách Mảng đếm (Frequency Array)

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

const int MAX_VAL = 100000007;
int freq[MAX_VAL];

int main() {
    freopen("chenhlech.INP", "r", stdin);
    freopen("chenhlech.OUT", "w", stdout);

    int n;
    cin >> n;

    int max_diff = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        int diff = abs(a - b);
        freq[diff]++;
        if (diff > max_diff) max_diff = diff;
    }

    int ans = 0;
    int max_freq = 0;

    // Chỉ cần duyệt đến max_diff thay vì toàn mảng
    for (int i = 0; i <= max_diff; i++) {
        if (freq[i] > max_freq) {
            max_freq = freq[i];
            ans = i;
        }
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n + D) (với D là giá trị chênh lệch lớn nhất)
• Space Complexity: O(D)

Nếu giá trị chênh lệch bị giới hạn trong một khoảng nhỏ (ví dụ $10^7$ như trong code mẫu), ta có thể dùng mảng một chiều freq để đếm trực tiếp. Khi đó, chỉ số của mảng chính là giá trị chênh lệch. Phương pháp này cực kỳ nhanh (truy cập trực tiếp O(1)) và chỉ cần duyệt lại mảng một lần để tìm giá trị lớn nhất. Tuy nhiên, nhược điểm là tốn bộ nhớ nếu giá trị chênh lệch quá lớn.

Cách Sử dụng Vector và Sắp xếp

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

int main() {
    freopen("chenhlech.INP", "r", stdin);
    freopen("chenhlech.OUT", "w", stdout);

    int n;
    cin >> n;
    vector<int> diffs(n);

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        diffs[i] = abs(a - b);
    }

    sort(diffs.begin(), diffs.end());

    int ans = diffs[0];
    int max_freq = 1;
    int current_freq = 1;

    for (int i = 1; i < n; i++) {
        if (diffs[i] == diffs[i-1]) {
            current_freq++;
        } else {
            if (current_freq > max_freq) {
                max_freq = current_freq;
                ans = diffs[i-1];
            }
            current_freq = 1;
        }
    }
    // Kiểm tra đoạn cuối cùng
    if (current_freq > max_freq) {
        ans = diffs[n-1];
    }

    cout << ans << endl;
    return 0;
}

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

Cách tiếp cận này lưu tất cả các giá trị chênh lệch vào một vector, sau đó sắp xếp vector đó. Khi các giá trị đã được sắp xếp, các số giống nhau sẽ đứng cạnh nhau, giúp ta dễ dàng đếm số lần lặp lại bằng cách duyệt một lượt. Độ phức tạp phụ thuộc chính vào bước sắp xếp, là O(n log n).

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 giai đoạn chính: (1) Tạo ra các giá trị chênh lệch từ input, (2) Tìm phần tử có tần suất xuất hiện nhiều nhất trong danh sách các giá trị đó.
• Việc sử dụng map là cách giải tổng quát nhất, không phụ thuộc vào phạm vi giá trị của input và dễ dàng cài đặt.
• Độ phức tạp time của các giải pháp thường bị chi phối bởi thuật toán sort hoặc structure map, đều nằm trong khoảng O(n log n).

Lỗi thường gặp

• Không xử lý đúng trường hợp có nhiều hơn một giá trị có cùng tần suất cao nhất. Tuy nhiên, dựa vào các giải pháp mẫu, yêu cầu bài toán dường như chỉ cần in ra một giá trị bất kỳ trong số đó (hoặc giá trị đầu tiên tìm thấy).
• Sử dụng mảng đếm không đúng cách nếu giá trị chênh lệch vượt quá kích thước mảng cho phép, dẫn đến lỗi tràn bộ nhớ (segmentation fault).
• Quên thư viện cần thiết như <map>, <vector>, hoặc <cmath> (cho hàm abs).