Hiểu bài toán

Cho một mảng gồm N số nguyên và Q truy vấn. Mỗi truy vấn cho một số k, nhiệm vụ là tìm chỉ số i (1-based) nhỏ nhất trong mảng sao cho giá trị tại đó a[i] ≤ k. Đảm bảo luôn có ít nhất một đáp án cho mỗi truy vấn.

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

Cách Brute Force (Duyệt toàn bộ)

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

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

    int q; cin >> q;
    while(q--) {
        int k; cin >> k;
        int ans = -1;
        for(int i=0; i<n; i++) {
            if(a[i] <= k) {
                ans = i + 1;
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

• Time Complexity: O(Q * N)
• Space Complexity: O(N)

Với mỗi truy vấn, duyệt tuần tự từ đầu mảng để tìm phần tử đầu tiên có giá trị ≤ k. Do Q và N có thể lên tới 10^6 và 10^5, độ phức tạp này quá cao (10^11 thao tác) và chắc chắn bị TLE.

Cách Mảng truy vấn tiền tố (Prefix Minimum)

#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);
    for(int i=0; i<n; i++) cin >> a[i];

    // Tạo mảng minFromLeft: minFromLeft[i] là giá trị nhỏ nhất từ 0 đến i
    vector<int> minFromLeft(n);
    minFromLeft[0] = a[0];
    for(int i=1; i<n; i++) {
        minFromLeft[i] = min(minFromLeft[i-1], a[i]);
    }

    int q; cin >> q;
    while(q--) {
        int k; cin >> k;
        int l = 0, r = n - 1;
        int res = -1;
        // Tìm chỉ số nhỏ nhất sao cho minFromLeft[mid] <= k
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(minFromLeft[mid] <= k) {
                res = mid;
                r = mid - 1; // Thử tìm nhỏ hơn nữa
            } else {
                l = mid + 1;
            }
        }
        cout << res + 1 << "\n";
    }
    return 0;
}

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

1. Xây dựng mảng minFromLeft với minFromLeft[i] là giá trị nhỏ nhất trong đoạn a[0...i]. Mảng này có tính chất không giảm (non-decreasing).
2. Với mỗi truy vấn k, ta dùng Binary Search (tìm kiếm nhị phân) trên mảng minFromLeft để tìm chỉ số i nhỏ nhất sao cho minFromLeft[i] <= k.
3. Vì minFromLeft là mảng đơn điệu, Binary Search cho kết quả chính xác. Nếu không tìm thấy, đảm bảo đề bài luôn có đáp án nên ta chỉ cần loát logic tìm phần tử đầu tiên thỏa mãn.

Cách Mảng truy vấn tiền tố 1-based (Optimized)

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

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

    int N;
    cin >> N;
    // mn[0] = INT_MAX để xử lý dễ dàng hơn (hoặc dùng vector size N+1)
    vector<int> mn(N + 1);
    mn[0] = INT_MAX;

    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        mn[i] = min(mn[i - 1], x);
    }

    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        int l = 1, r = N, ans = N;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mn[mid] <= k) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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

Cách tiếp cận tương tự như 'Prefix Minimum' nhưng sử dụng chỉ số 1-based cho mảng phụ mn. Điều này giúp mã nguồn nhất quán với đầu ra yêu cầu (1-based). Logic Binary Search vẫn giữ nguyên: tìm vị trí đầu tiên trong dãy mn có giá trị ≤ k. Do mn không giảm, nếu mn[mid] thỏa mãn, mọi chỉ số từ mid trở về trước đều thỏa mãn nên ta thu hẹp khoảng cách tìm kiếm về bên trái.

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 bằng cách tiền xử lý để biến đổi dữ liệu thành dạng đơn điệu (monotonic), từ đó áp dụng Binary Search.
• Mảng minFromLeft (giá trị nhỏ nhất tính từ đầu) có tính chất không giảm, cho phép tìm kiếm nhị phân để tìm vị trí đầu tiên thỏa mãn điều kiện giá trị ≤ k.

Lỗi thường gặp

• Lỗi chỉ số (Indexing): Chú ý giữa mảng 0-based (trong C++) và yêu cầu output 1-based. Cần cộng trừ 1 cho hợp lý.
• Biến giới hạn trong Binary Search: Sai lầm khi gán r = mid thay vì r = mid - 1 có thể dẫn đến vòng lặp vô hạn hoặc sai kết quả.