Hiểu bài toán

Bài toán yêu cầu đếm số lượng đoạn con liên tiếp trong mảng gồm n số nguyên sao cho tổng các phần tử trong đoạn con không vượt quá một giá trị cho trước K. Mảng có thể chứa các số nguyên, nhưng các giải pháp chấp nhận cho thấy các số này là số không âm (mặc dù điều này không được nói rõ trong đề bài).

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

Cách Binary Search on Prefix Sums

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000011];
ll f[1000011] ;
int main()
{
   freopen("BOOKS.INP","r",stdin) ;
   freopen("BOOKS.OUT","w",stdout) ;
    ll n ,k ,luu=0;
     f[0]=0 ;
    cin>>n>>k;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        f[i]=f[i-1]+a[i] ;
        }
        for(ll i=1;i<=n;i++){
            ll r=i ,l=n ,MAX=0;
            while(r<=l){
                ll m = (r+l)/2 ;
                ll g=f[m]-f[i-1] ;
                if(g<=k){
                    r=m+1 ;
                   MAX=max(MAX,m) ;
                }else l=m-1 ;
            }
            if(MAX!=0){
            luu+=MAX-i+1 ;
            }
        }
        cout<<luu ;
    return 0;
}

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

Cách tiếp cận này sử dụng mảng tổng tiền tố (prefix sum). Với mỗi vị trí bắt đầu i, ta dùng tìm kiếm nhị phân (Binary Search) để tìm vị trí kết thúc j xa nhất sao cho tổng từ i đến j (tính bằng f[j] - f[i-1]) nhỏ hơn hoặc bằng K. Số đoạn con bắt đầu tại i thỏa mãn là (j - i + 1). Độ phức tạp là O(n log n) do có n lần tìm kiếm nhị phân.

Cách Two Pointers (Sliding Window)

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

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

    freopen("BOOKS.INP", "r", stdin);
    freopen("BOOKS.OUT", "w", stdout);

    long long n, K;
    cin >> n >> K;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long s = 0;      // tổng hiện tại
    long long ans = 0;    // số cách
    int l = 1;            // đầu đoạn

    for (int r = 1; r <= n; r++) {
        s += a[r];

        // nếu tổng > K thì dồn l lên cho tới khi s <= K
        while (l <= r && s > K) {
            s -= a[l];
            l++;
        }

        // giờ tất cả các đoạn kết thúc ở r, bắt đầu từ l..r đều có tổng <= K
        ans += (r - l + 1);
    }

    cout << ans;
    return 0;
}

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

Sử dụng kỹ thuật hai con trỏ (Sliding Window). Duyệt con trỏ r từ 1 đến n để mở rộng đoạn con về phía phải. Nếu tổng hiện tại vượt quá K, ta di chuyển con trỏ l sang phải để thu hẹp đoạn con cho đến khi tổng trở lại <= K. Với mỗi r, tất cả các đoạn con kết thúc tại r mà bắt đầu từ l đến r đều hợp lệ. Do mỗi phần tử được thêm vào và bớt đi tối đa 1 lần, độ phức tạp là O(n).

Cách Two Pointers (Variant)

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

int main() {
    ifstream fin("BOOKS.INP");
    ofstream fout("BOOKS.OUT");

    int n;
    long long K;
    fin >> n >> K;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) fin >> a[i];

    long long count = 0, sum = 0;
    int l = 0;

    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > K && l <= r) {
            sum -= a[l];
            l++;
        }
        // Đoạn con [l..r] thỏa
        count += r - l + 1;
    }

    fout << count << "\n";

    fin.close();
    fout.close();
    return 0;
}

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

Đây là biến thể của thuật toán hai con trỏ sử dụng chỉ số 0-based. Logic tương tự: duyệt r, cập nhật tổng, và điều chỉnh l về bên phải nếu tổng quá lớn. Với mỗi bước, số đoạn con hợp lệ kết thúc tại r được cộng dồn vào kết quả.

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

Bài học kinh nghiệm

• Tổng các số không âm cho phép sử dụng kỹ thuật hai con trỏ (Sliding Window) một cách hiệu quả, vì khi di chuyển con trỏ phải sang phải, tổng chỉ tăng lên.
• Biến đổi bài toán thành việc tính tổng số đoạn con thỏa mãn điều kiện tổng <= K.

Lỗi thường gặp

• Sử dụng biến số nguyên 32-bit để lưu tổng, dẫn đến tràn số (overflow) nếu tổng các phần tử vượt quá giới hạn của int. Cần dùng kiểu dữ liệu lớn hơn như long long.
• Lỗi chỉ số mảng (off-by-one error) khi chuyển đổi giữa các cách tiếp cận (ví dụ: 1-based indexing trong Binary Search và 0-based trong Sliding Window).