Hiểu bài toán

Cho một mảng một chiều gồm n phần tử (2 ≤ n ≤ 1000). Nhiệm vụ là tìm giá trị trung bình nhỏ nhất và lớn nhất của tất cả các dãy con liên tiếp có độ dài ít nhất 2 phần tử. Đầu ra là hai số thực làm tròn đến 3 chữ số thập phân, cách nhau bởi dấu cách, trong đó số đầu tiên là trung bình nhỏ nhất và số thứ hai là trung bình lớn nhất.

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

Cách Brute Force với tiền tố tổng (Prefix Sum)

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), s(n);

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

    s[0] = a[0];
    for (int i = 1; i < n; i++)
        s[i] = s[i - 1] + a[i];

    double min_avg = 1e18, max_avg = -1e18;

    for (int l = 0; l < n; l++) {
        for (int r = l + 1; r < n; r++) {
            long long sum = s[r] - (l ? s[l - 1] : 0);
            double avg = (double)sum / (r - l + 1);
            min_avg = min(min_avg, avg);
            max_avg = max(max_avg, avg);
        }
    }

    cout << fixed << setprecision(3) << min_avg << " " << max_avg;
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Đầu tiên, ta xây dựng mảng tổng tiền tố s để tính tổng của bất kỳ dãy con nào trong thời gian O(1). s[i] lưu tổng các phần tử từ a[0] đến a[i]. Để tính tổng dãy con từ chỉ số l đến r, ta dùng công thức s[r] - s[l-1] (nếu l=0 thì tổng là s[r]). Sau đó, ta duyệt qua tất cả các cặp (l, r) sao cho l < r (đảm bảo dãy con có ít nhất 2 phần tử), tính giá trị trung bình và cập nhật giá trị nhỏ nhất và lớn nhất. Độ phức tạp thời gian là O(n^2) do có 2 vòng lặp lồng nhau, và độ phức tạp không gian là O(n) để lưu mảng tổng.

Cách Brute Force không dùng tiền tố tổng

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

int main()
{
    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    double mn=INT_MAX,mx=INT_MIN;
    for(int i=1;i<=n;i++) {
        long long sum = 0;
        for(int j=i;j<=n;j++) {
            sum += a[j];
            if (j - i + 1 >= 2) {
                 double g=1.0*sum/(j-i+1);
                 mn=min(mn,g);
                 mx=max(mx,g);
            }
        }
    }
    cout<<setprecision(3)<<fixed<<mn<<" "<<mx;
}

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

Cách này cũng duyệt qua tất cả các dãy con liên tiếp nhưng không cần mảng tổng tiền tố. Thay vào đó, với mỗi điểm bắt đầu i, ta duyệt điểm kết thúc j từ i trở đi, vừa cập nhật tổng của dãy con hiện tại (sum += a[j]) vừa tính trung bình. Điều này tránh được chi phí xây dựng mảng tiền tố ban đầu và logic tính tổng có thể dễ hiểu hơn một chút. Tuy nhiên, về tổng thể độ phức tạp vẫn là O(n^2) và không tối ưu hơn cách dùng prefix sum.

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

Bài học kinh nghiệm

• Bài toán yêu cầu duyệt qua tất cả các dãy con có độ dài >= 2, vì vậy giải thuật O(n^2) là chấp nhận được với n ≤ 1000.
• Sử dụng mảng tổng tiền tố (Prefix Sum Array) giúp tính tổng của bất kỳ dãy con nào trong thời gian O(1) sau khi đã xử lý ban đầu.
• Cần lưu ý xử lý kiểu dữ liệu. Tổng các phần tử có thể lên tới 10^9 * 1000 = 10^12, nên cần dùng long long để tránh tràn số nguyên. Giá trị trung bình cần độ chính xác cao nên dùng double.

Lỗi thường gặp

• Quên kiểm tra điều kiện dãy con có ít nhất 2 phần tử (độ dài >= 2) khi tính trung bình.
• Sử dụng int cho biến lưu tổng dẫn đến tràn số nếu các giá trị đầu vào lớn.
• Sai lệch trong việc tính chỉ số khi dùng mảng tổng tiền tố (ví dụ: s[r] - s[l] thay vì s[r] - s[l-1], hoặc xử lý sai trường hợp l=0).
• Định dạng đầu ra không đúng yêu cầu (không in số thập phân làm tròn đến 3 chữ số, hoặc thiếu dấu cách).