Hiểu bài toán

Bài toán yêu cầu tìm chênh lệch chiều cao nhỏ nhất giữa hai học sinh trong một trường học. Với n học sinh (1 ≤ n ≤ 10^5) và chiều cao của từng học sinh (1 ≤ hi ≤ 10^9), ta cần chọn một cặp hai học sinh sao cho hiệu số chiều cao của họ là nhỏ nhất. Nói cách khác, cần tìm giá trị |hi - h_j| nhỏ nhất với i ≠ j.

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

Cách Brute Force (Duyệt tất cả cặp)

#include <stdio.h>
#include <limits.h>

int main() {
    int n;
    scanf("%d", &n);
    int h[100000];
    for (int i = 0; i < n; i++) scanf("%d", &h[i]);

    int min_diff = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = h[i] - h[j];
            if (diff < 0) diff = -diff;
            if (diff < min_diff) min_diff = diff;
        }
    }
    printf("%d\n", min_diff);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Phương pháp này thử tất cả các cặp (i, j) có thể và tính chênh lệch chiều cao của chúng, sau đó tìm giá trị nhỏ nhất. Với n lên tới 10^5, độ phức tạp O(n^2) sẽ thực hiện khoảng 10^10 phép tính, vượt quá giới hạn thời gian (thường là 1 giây). Do đó, phương pháp này không khả thi.

Cách Sắp xếp và So sánh kề nhau

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    scanf("%d", &n);
    int h[100000];
    for (int i = 0; i < n; i++) scanf("%d", &h[i]);

    qsort(h, n, sizeof(int), cmp);

    int min_diff = INT_MAX;
    for (int i = 1; i < n; i++) {
        int diff = h[i] - h[i - 1];
        if (diff < min_diff) min_diff = diff;
    }
    printf("%d\n", min_diff);
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(1) hoặc O(n) (tùy vào thư viện qsort)

Nếu ta sắp xếp mảng chiều cao tăng dần, cặp hai học sinh có chênh lệch nhỏ nhất chắc chắn phải là hai số kề nhau trong mảng đã sắp xếp. Ví dụ: nếu mảng là [1, 5, 10], cặp (1, 5) chênh 4, cặp (5, 10) chênh 5. Cặp (1, 10) chênh 9. Ta chỉ cần duyệt qua mảng đã sắp xếp và so sánh các cặp kề nhau để tìm chênh lệch nhỏ nhất. Độ phức tạp do hàm sắp xếp quyết định là O(n log n), rất hiệu quả cho n = 10^5.

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

Bài học kinh nghiệm

• Bài toán tìm chênh lệch nhỏ nhất giữa hai phần tử trong mảng có thể quy về bài toán tìm phần tử gần nhau nhất sau khi sắp xếp.
• Sự khác biệt giữa hai số bất kỳ trong mảng đã sắp xếp không thể nhỏ hơn sự khác biệt giữa hai số kề nhau trong đoạn nằm giữa chúng.

Lỗi thường gặp

• Không xử lý trường hợp n < 2 (mặc dù đề bài thường đảm bảo n >= 2, nhưng code nên chặt chẽ).
• Sử dụng biến lưu chênh lệch có thể tràn số (integer overflow) nếu giá trị hi rất lớn và âm, nhưng trong bài này hi là số dương nên trừ đơn giản.
• Quên cập nhật biến kết quả sau khi tính toán.