Hiểu bài toán

Cho một mảng gồm n số nguyên dương a[1..n] và một số nguyên dương k. Nhiệm vụ tìm số nguyên dương x sao cho có ít nhất k đoạn con liên tiếp có tổng các phần tử không vượt quá x. Nói cách khác, tìm giá trị x nhỏ nhất thỏa mãn số lượng các đoạn con (i, j) với 1 <= i <= j <= n thỏa mãn sum(a[i..j]) <= x là >= k.

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

Cách Brute Force (Đếm trực tiếp)

// Chỉ mang tính minh họa, không có trong bài nộp
// Duyệt tất cả các đoạn con, kiểm tra tổng, đếm
long long count_subarrays_brute(long long limit) {
    long long cnt = 0;
    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = i; j <= n; j++) {
            sum += a[j];
            if (sum <= limit) cnt++;
            else break; 
        }
    }
    return cnt;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Cách tiếp cận này duyệt qua tất cả các đoạn con có thể có (i, j). Với mỗi đoạn con, tính tổng và nếu tổng <= x thì tăng biến đếm. Cách này quá chậm với n lớn (ví dụ n=10^5).

Cách Binary Search + Two Pointers (Sliding Window)

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

long long a[1000009];
int n;
long long k;

// Hàm đếm số đoạn con có tổng <= x
count_function(long long x){
    long long s = 0;
    int l = 1;
    long long ans = 0;
    for(int r = 1; r <= n; r++){
        s += a[r];
        while(s > x){
            s -= a[l];
            l++;
        }
        ans += r - l + 1;
    }
    return ans;
}

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

    cin >> n >> k;
    long long r = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        r += a[i];
    }

    long long l = 0;
    long long ans = r;

    while(l <= r){
        long long mid = (l + r) / 2;
        if(count_function(mid) >= k){
            ans = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }

    cout << ans << "\n";
    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất được sử dụng trong các bài nộp.

1. Binary Search (Tìm kiếm nhị phân): Ta tìm giá trị x tối thiểu. Có thể thấy nếu x thỏa mãn điều kiện (có >= k đoạn con), thì mọi giá trị x' > x cũng thỏa mãn. Tính đơn điệu này cho phép áp dụng tìm kiếm nhị phân trên giá trị x. Miền tìm kiếm là [0, tổng tất cả các phần tử].
2. Hàm kiểm tra (Check function): Để kiểm tra xem với một giá trị x cụ thể có bao nhiêu đoạn con có tổng <= x, ta sử dụng kỹ thuật Two Pointers (Sliding Window).
   • Duyệt cột phải r từ 1 đến n.
   • Duy trì cột trái l sao cho tổng đoạn a[l..r] luôn <= x.
   • Nếu tổng vượt quá x, ta dịch chuyển l sang phải cho đến khi tổng <= x.
   • Với mỗi cột r, số đoạn con kết thúc tại r có tổng <= x chính là r - l + 1.
   • Cộng dồn số đoạn con này vào tổng.
3. Tối ưu: Trong hàm kiểm tra, nếu số đoạn con đã vượt quá k, ta có thể dừng sớm và trả về true (để tăng tốc độ).

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

Bài học kinh nghiệm

• Bài toán có tính đơn điệu: Nếu giá trị x đủ lớn để có >= k đoạn con thì mọi giá trị lớn hơn cũng đủ. Điều này cho phép sử dụng Binary Search.
• Kỹ thuật Two Pointers (Sliding Window) hiệu quả để đếm số đoạn con có tổng <= X trong mảng dương: Với mỗi điểm cuối r, tìm điểm bắt đầu l xa nhất sao cho tổng đoạn a[l..r] <= X. Số đoạn con kết thúc tại r thỏa mãn điều kiện là r - l + 1.
• Binary Search kết hợp với hàm kiểm tra O(n) tạo ra thuật toán O(n log Sum), nhanh hơn nhiều so với O(n^2).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu sai: Tổng các phần tử có thể vượt quá giới hạn của kiểu int (2^31-1). Cần dùng long long (trong C++).
• Lỗi biên trong Sliding Window: Khi cập nhật chỉ số左 cột l, cần đảm bảo rằng l không vượt quá r.
• Lỗi logic Binary Search: Cài đặt sai công thức mid = l + (r - l) / 2 hoặc sai điều kiện cập nhật l và r. Phân tích kỹ điều kiện 'Tìm giá trị nhỏ nhất thỏa mãn P' để viết đúng điều kiện if/else.