Hiểu bài toán

Cho một danh sách ~n~ học sinh với chiều cao ~h_i~. Cần chọn ngẫu nhiên 5 học sinh sao cho chênh lệch giữa người cao nhất và người thấp nhất trong nhóm là nhỏ nhất có thể. Nói cách khác, tìm một tập hợp con 5 phần tử trong mảng sao cho hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất của tập con đó là nhỏ nhất.

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

Cách Brute Force

void brute_force(vector<long long>& a) {
    long long n = a.size();
    long long ans = LLONG_MAX;
    // Duyệt tất cả các tổ hợp 5 phần tử
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    for (int m = l + 1; m < n; m++) {
                        // Tìm min và max trong 5 phần tử này
                        long long current_max = max({a[i], a[j], a[k], a[l], a[m]});
                        long long current_min = min({a[i], a[j], a[k], a[l], a[m]});
                        ans = min(ans, current_max - current_min);
                    }
                }
            }
        }
    }
    cout << ans;
}

• Time Complexity: O(n^5)
• Space Complexity: O(1)

Phương pháp này thử tất cả các cách chọn 5 học sinh khác nhau từ ~n~ học sinh. Với mỗi tổ hợp, ta tính chênh lệch giữa học sinh cao nhất và thấp nhất, sau đó cập nhật kết quả nhỏ nhất. Tuy nhiên, do ~n~ có thể lên tới 100,000, độ phức tạp ~O(n^5)~ là quá lớn và không thể chạy được trong thời gian cho phép.

Cách Sắp xếp và Sliding Window (Đơn giản)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> h(n);
    for(int i = 0; i < n; i++) {
        cin >> h[i];
    }

    // Bước 1: Sắp xếp mảng chiều cao
    sort(h.begin(), h.end());

    // Bước 2: Duyệt tìm đoạn liên tiếp độ dài 5 có hiệu nhỏ nhất
    long long ans = LLONG_MAX;
    for(int i = 0; i <= n - 5; i++) {
        ans = min(ans, h[i + 4] - h[i]);
    }

    cout << ans;
    return 0;
}

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

Bài toán có thể giải quyết hiệu quả bằng cách:

1. Sắp xếp lại mảng chiều cao theo thứ tự tăng dần.
2. Sau khi sắp xếp, để chọn được 5 học sinh sao cho chênh lệch giữa cao nhất và thấp nhất nhỏ nhất, ta cần chọn 5 học sinh có chiều cao 'gần nhau' nhất trong mảng đã sắp xếp. Điều này có nghĩa là 5 học sinh được chọn phải là 5 phần tử liên tiếp trong mảng đã sắp xếp.
3. Ta duyệt một cửa sổ trượt (sliding window) có độ dài 5 qua mảng. Với mỗi vị trí bắt đầu ~i~, học sinh thấp nhất trong nhóm là ~h[i]~ và cao nhất là ~h[i+4]~. Hiệu là ~h[i+4] - h[i]~. Ta chỉ cần tìm giá trị hiệu nhỏ nhất này.

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

Bài học kinh nghiệm

• Bài toán có thể giảm độ phức tạp từ O(n^5) xuống O(n log n) bằng cách sắp xếp dữ liệu trước.
• Sau khi sắp xếp, lựa chọn tối ưu cho 5 học sinh luôn là một đoạn liên tiếp độ dài 5 trong mảng.

Lỗi thường gặp

• Quên kiểm tra điều kiện biên (ví dụ: vòng lặp chạy đến ~i <= n - 5~ thay vì ~i < n~).
• Sử dụng biến lưu kết quả có kiểu dữ liệu quá nhỏ (ví dụ: ~int~) dẫn đến tràn số khi ~h_i~ lên tới 10^9.