Hiểu bài toán

Một bệnh viện có ban đầu k bệnh nhân F0. Trong n ngày tiếp theo, mỗi ngày i có a[i] bệnh nhân mới được phát hiện và b[i] bệnh nhân được chữa khỏi (ra viện). Bệnh nhân mới được phát hiện sẽ được thêm vào cùng ngày đó. Yêu cầu tìm ngày đầu tiên số lượng F0 giảm về 0 hoặc âm (tức là bệnh viện đã hết F0). Nếu sau n ngày vẫn còn F0 thì in ra -1.

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

Cách Mô phỏng cơ bản

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

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

    int current = k;
    for(int i=0;i<n;i++){
        current += a[i];
        current -= b[i];
        if(current <= 0){
            cout << i+1 << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

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

Sử dụng biến current để lưu số lượng F0 hiện tại. Duyệt qua từng ngày, cập nhật số lượng F0 bằng cách thêm số ca mới (a[i]) và trừ số ca khỏi (b[i]). Nếu sau khi cập nhật current <= 0, in ra ngày đó (chỉ số + 1) và kết thúc. Nếu duyệt hết n ngày mà current vẫn lớn hơn 0, in ra -1.

Cách Tối ưu bộ nhớ

#include <bits/stdc++.h>
using namespace std;
long long n,k,a[1000006],b[1000006],f0,f1;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>k>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    long long f0=k;
    for(int i=1;i<=n;i++)
    {
        f0+=a[i];
        f0-=b[i];
        if(f0<=0)
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
}

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

Cách tiếp cận này tương tự cách 1 nhưng sử dụng mảng tĩnh lớn thay vì vector để lưu trữ dữ liệu đầu vào. Logic tính toán vẫn giữ nguyên: cộng trừ trực tiếp vào biến f0 (biến lưu F0 hiện tại) và kiểm tra điều kiện dừng.

Cách Xử lý dữ liệu lớn (Kiểu 2)

#include <bits/stdc++.h>
using namespace std;
long long n,k,a[1000006],b[1000006];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>k>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    long long current = k;
    for(int i=1;i<=n;i++)
    {
        current += a[i];
        current -= b[i];
        if(current <= 0)
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
}

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

Giải pháp chuẩn cho các bài toán mô phỏng quy mô lớn. Sử dụng long long để tránh tràn số nếu số lượng bệnh nhân quá lớn. Sử dụng mảng tĩnh hoặc vector để lưu a và b. Tuy nhiên, có thể tối ưu hơn bằng cách không cần lưu mảng b (xem phần 'Key Insights').

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu tìm ngày đầu tiên, do đó ta có thể dừng lại ngay khi tìm thấy kết quả mà không cần duyệt hết toàn bộ n ngày.
• Vì số lượng F0 chỉ giảm khi trừ đi b[i], ta có thể tối ưu bộ nhớ bằng cách không cần mảng b. Ta chỉ cần đọc b[i] và trừ ngay lập tức vào biến đang lưu F0. Tuy nhiên, với n lớn, việc đọc vào a vẫn cần mảng (hoặc dùng vector để tối ưu cache).
• Cần dùng biến có kiểu dữ liệu lớn (long long) nếu k và a[i] (hoặc b[i]) có thể lớn (ví dụ lên tới 10^9).

Lỗi thường gặp

• Sử dụng kiểu int导致 tràn số (overflow) nếu tổng số F0 vượt quá 2*10^9.
• Quên in ra ngày hiện tại cộng thêm 1 (do chỉ số mảng bắt đầu từ 0).
• Lỗi logic khi so sánh: đề bài yêu cầu ngày hết F0, tức là số lượng F0 <= 0. Một số sai lầm có thể là so sánh < 0 thay vì <= 0.