Editorial for height: Đếm số học sinh thấp hơn

Hiểu bài toán

Bài toán yêu cầu với mỗi học sinh i, đếm số lượng học sinh khác có chiều cao nhỏ hơn Ai. Nói cách khác, với mỗi phần tử trong mảng A, ta cần tìm số lượng phần tử có giá trị nhỏ hơn nó. Dữ liệu đầu vào có N lên tới 10^5, chiều cao Ai lên tới 10^9.

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

Cách Brute Force

#include <iostream>
#include <vector>

using namespace std;

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

    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (a[j] < a[i]) {
                cnt++;
            }
        }
        cout << cnt << " ";
    }
    return 0;
}

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

Với mỗi học sinh i, duyệt qua tất cả các học sinh j từ 1 đến N. Nếu A[j] < A[i] thì tăng biến đếm. Cách này đơn giản nhưng quá chậm với N lớn (N = 10^5).

Cách Sắp xếp và Binary Search (Lower Bound)

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

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

    int N;
    cin >> N;

    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        B[i] = A[i];
    }

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

    for (int i = 0; i < N; i++) {
        // lower_bound trả về iterator đến phần tử đầu tiên >= A[i]
        // Số lượng phần tử nhỏ hơn A[i] chính là chỉ số của phần tử đó
        int cnt = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
        cout << cnt << " ";
    }

    return 0;
}

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

1. Tạo một mảng phụ B bằng với mảng A.
2. Sắp xếp mảng B tăng dần.
3. Với mỗi giá trị A[i] trong mảng gốc, dùng hàm lower_bound trên mảng B để tìm vị trí đầu tiên có giá trị >= A[i].
4. Số lượng phần tử nhỏ hơn A[i] chính là chỉ số (index) của vị trí đó. Ví dụ: B = [110, 120, 130, 140]. Với A[i] = 130, lower_bound tìm thấy chỉ số 2 (giá trị 130). Có 2 phần tử nhỏ hơn (110, 120).

Cách Lưu trữ vị trí ban đầu sau khi sắp xếp

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

int main() {
    int n;
    cin >> n;

    // pair.first là chiều cao, pair.second là chỉ số ban đầu
    vector<pair<long long, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }

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

    vector<int> res(n);
    int dem = 0;

    for (int i = 0; i < n; i++) {
        // Nếu gặp giá trị khác biệt với giá trị trước đó, cập nhật số đếm
        // Số đếm tại vị trí i chính là i (vì mảng đã sắp xếp)
        if (i > 0 && a[i].first != a[i-1].first) 
            dem = i;
        // Nếu bằng giá trị trước đó, dem giữ nguyên (không tăng)
        res[a[i].second] = dem;
    }

    for (int i = 0; i < n; i++)
        cout << res[i] << " ";

    return 0;
}

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

1. Tạo mảng các cặp (chiều cao, chỉ số ban đầu) và sắp xếp theo chiều cao.
2. Duyệt mảng đã sắp xếp. Với mỗi phần tử tại vị trí i:
   • Nếu không có phần tử nào trước đó bằng nó, số lượng học sinh thấp hơn là i.
   • Nếu có phần tử trước đó bằng nó, số lượng học sinh thấp hơn giữ nguyên bằng giá trị của phần tử đầu tiên trong dãy bằng nhau đó.
3. Gán kết quả vào vị trí ban đầu đã lưu trong pair.second. Cách này cũng O(N log N) nhưng khác biệt về mặt kỹ thuật so với cách dùng lower_bound.

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

Bài học kinh nghiệm

• Bài toán đếm số lượng phần tử nhỏ hơn phần tử hiện tại có thể giải quyết hiệu quả bằng cách sắp xếp.
• Sử dụng hàm 'lower_bound' trong C++ là cách cài đặt ngắn gọn và hiệu quả để tìm số lượng phần tử nhỏ hơn (hoặc bằng).
• Nếu giá trị có thể bị trùng lặp, cần xử lý riêng để không đếm các phần tử bằng nhau.

Lỗi thường gặp

• Sử dụng thuật toán O(N^2)導致 Time Limit Exceeded với N lớn.
• Quên xử lý các giá trị bằng nhau (duplicate values) khi dùng mảng sắp xếp trực tiếp (ví dụ: cách 2 tự viết vòng lặp đếm).
• Độ lớn của A_i lên tới 10^9 nên cần dùng kiểu dữ liệu 'long long' cho chiều cao nếu dùng mảng kết hợp với chỉ số (pair).