Hiểu bài toán

Bài toán yêu cầu tìm một độ cao bay (từ 1 đến H) sao cho số lượng chướng ngại vật con chim phải phá vỡ là ít nhất. Có N chướng ngại vật, mỗi cái là một măng đá (mọc từ đáy lên, dương) hoặc nhũ đá (mọc từ trần xuống, âm). Con chim bay ở độ cao $y$ sẽ phá vỡ:

1. Măng đá có độ dài $l > 0$ nếu $y \le l$.
2. Nhũ đá có độ dài $|l|$ (giá trị âm $l$) nếu $y \ge H + l + 1$ (vì nhũ đá nằm ở khoảng $[H - |l| + 1, H]$). Ta cần tính số chướng ngại vật phải phá cho từng độ cao $y \in [1, H]$ và tìm giá trị nhỏ nhất.

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

Cách Sử dụng mảng cộng dồn (Difference Array)

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

int main() {
    int n, h;
    cin >> n >> h;
    // dp[i] là mảng cộng dồn, lưu số lượng chướng ngại vật tại độ cao i
    vector<int> dp(h + 2, 0);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x > 0) { // Măng đá: phá nếu y <= x
            dp[1]++;
            if (x + 1 <= h) dp[x + 1]--; // Dừng phá khi y > x
        } else { // Nhũ đá: phá nếu y >= h + x + 1 (vì x là số âm)
            int stick_len = -x;
            int start_height = h - stick_len + 1;
            dp[start_height]++;
            dp[h + 1]--; // Tăng đến hết độ cao H
        }
    }

    int min_obstacles = n;
    int current_obstacles = 0;
    for (int y = 1; y <= h; ++y) {
        current_obstacles += dp[y];
        if (current_obstacles < min_obstacles) {
            min_obstacles = current_obstacles;
        }
    }
    cout << min_obstacles;
    return 0;
}

• Time Complexity: O(N + H)
• Space Complexity: O(H)

Cách tiếp cận này tối ưu hóa việc tính toán bằng cách sử dụng kỹ thuật 'difference array' (mảng cộng dồn).

• Thay vì cộng dồn trực tiếp cho từng độ cao (O(N*H)), ta chỉ đánh dấu điểm bắt đầu và kết thúc của vùng bị ảnh hưởng.
• Với măng đá độ dài $l$ (giá trị $x$ dương): Nó ảnh hưởng các độ cao từ $1$ đến $l$. Ta cộng 1 vào dp[1] và trừ 1 vào dp[l+1].
• Với nhũ đá độ dài $l$ (giá trị $x$ âm): Nó ảnh hưởng các độ cao từ $H-l+1$ đến $H$. Ta cộng 1 vào dp[H-l+1] và trừ 1 vào dp[H+1].
• Sau khi xử lý hết các chướng ngại vật, ta duyệt mảng dp một lần để tính tổng tiền tố (prefix sum). Giá trị current_obstacles tại mỗi độ cao chính là số chướng ngại vật cần phá ở độ cao đó. Ta cập nhật giá trị nhỏ nhất.

Cách Brute Force (Tối giản)

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

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

    int min_obs = n;
    // Duyệt qua từng độ cao có thể bay
    for (int y = 1; y <= h; ++y) {
        int current_obs = 0;
        for (int x : a) {
            if (x > 0) { // Măng đá
                if (y <= x) current_obs++;
            } else { // Nhũ đá
                if (y >= h + x + 1) current_obs++; // x là số âm
            }
        }
        min_obs = min(min_obs, current_obs);
    }
    cout << min_obs;
    return 0;
}

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

Đây là giải thuật trực tiếp nhất, mô phỏng lại yêu cầu bài toán một cách hoàn chỉnh.

• Ta duyệt qua từng độ cao $y$ từ 1 đến $H$.
• Với mỗi độ cao, ta duyệt qua tất cả $N$ chướng ngại vật để đếm xem có bao nhiêu cái bị con chim va phải.
• Điều kiện kiểm tra:
  • Măng đá ($x > 0$): Va phải nếu $y \le x$.
  • Nhũ đá ($x < 0$): Va phải nếu $y \ge H + x + 1$.
• Phương pháp này đúng nhưng quá chậm vì $N$ và $H$ có thể lên tới $10^5$, dẫn đến $10^{10}$ phép toán, chắc chắn gây Timeout.

Cách Sử dụng Prefix Sum (Mảng tần suất)

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

int main() {
    int n, h;
    cin >> n >> h;
    vector<int> cnt(h + 2, 0);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x >= 0) {
            cnt[1] += 1;
            cnt[x + 1] -= 1;
        } else {
            int l = -x;
            cnt[h - l + 1] += 1;
            cnt[h + 1] -= 1;
        }
    }

    for (int i = 1; i <= h; ++i) {
        cnt[i] += cnt[i - 1];
    }

    int ans = *min_element(cnt.begin() + 1, cnt.begin() + h + 1);
    cout << ans;
    return 0;
}

• Time Complexity: O(N + H)
• Space Complexity: O(H)

Đây là biến thể của phương pháp Difference Array.

• Thay vì dùng một mảng dp để cộng dồn rồi cộng dồn lại một lần nữa khi duyệt, ta có thể dùng trực tiếp mảng cnt.
• Ban đầu, cnt[i] sẽ là độ chênh lệch (delta) so với độ cao trước đó.
• Ví dụ: Măng đá độ dài 3. Ta tăng cnt[1] và giảm cnt[4]. Khi duyệt từ 1 đến H, cnt[1] là số lượng bắt đầu, cnt[2] là cnt[1] + cnt[2] (mặc định là 0), cnt[3] vẫn giữ giá trị, cnt[4] giảm đi.
• Cuối cùng, ta chỉ cần tìm giá trị nhỏ nhất trong mảng cnt từ index 1 đến H.
• Code mẫu của TienBac và tieuc908 là ví dụ điển hình của phương pháp này.

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

Bài học kinh nghiệm

• Vấn đề có thể được coi là bài toán tính giá trị của một hàm trên miền [1, H]. Hàm này có tính chất 'step function' (bậc thang), tăng/giảm đột ngột ở các điểm ngưỡng.
• Kỹ thuật Difference Array (hoặc Prefix Sum Array) là chìa khóa để giảm độ phức tạp từ O(N*H) xuống O(N+H). Thay vì tính toán lặp lại cho mỗi độ cao, ta chỉ cần đánh dấu các sự kiện bắt đầu/kết thúc của các đoạn bị ảnh hưởng.

Lỗi thường gặp

• Xử lý sai điều kiện biên cho nhũ đá: Độ cao bắt đầu của nhũ đá là H - độ_dài + 1. Nếu tính sai, ta có thể nhầm lẫn giữa các mức độ cao.
• Lỗi truy cập mảng: Khi đánh dấu kết thúc, cần đảm bảo chỉ số không vượt quá H+1. Ví dụ với măng đá độ dài x, ta trừ vào index x+1 (nếu x+1 <= H). Nếu x lớn hơn H, ta không cần trừ vì nó ảnh hưưởng đến hết chiều cao của hang.
• Quên cập nhật giá trị nhỏ nhất ngay khi tính xong prefix sum cho từng độ cao.