Tóm tắt đề bài

Cho dãy số nguyên \(A\) gồm \(N\) phần tử và hai số nguyên \(L, R\). Tìm giá trị trung bình cộng (AVERAGE) lớn nhất của một đoạn con liên tiếp có độ dài \(k\) thỏa mãn \(L \le k \le R\).

• Công thức tính AVERAGE của đoạn từ \(u\) đến \(v\): \(AVERAGE(u, v) = \frac{\sum_{i=u}^v A_i}{v - u + 1}\).
• Giới hạn: \(N \le 10^6\), \(|A_i| \le 10^9\), \(1 \le L \le R \le N\).

Phân tích

• Thách thức: Việc tìm trực tiếp đoạn con có trung bình cộng lớn nhất trong khoảng độ dài \([L, R]\) với \(N=10^6\) là rất khó nếu sử dụng các cách duyệt thông thường (\(O(N^2)\) hoặc \(O(N \log N)\) với cấu trúc dữ liệu phức tạp).
• Ý tưởng chủ đạo: Sử dụng phương pháp Chặt nhị phân trên kết quả (Binary Search on Answer).
• Biến đổi toán học: Giả sử ta đang kiểm tra xem có tồn tại đoạn con nào có trung bình cộng ít nhất là \(x\) hay không:

• Đặt \(B_i = A_i - x\). Bài toán trở thành: Tìm xem có tồn tại đoạn con liên tiếp của dãy \(B\) có độ dài trong khoảng \([L, R]\) mà tổng các phần tử không âm (\(\ge 0\)).
• Để tính tổng đoạn con nhanh chóng, ta dùng mảng tiền tố (prefix sum) \(P\) của dãy \(B\): \(P_i = \sum_{j=1}^i B_j\). Tổng đoạn con từ \(u\) đến \(v\) là \(P_v - P_{u-1}\) với \(L \le v - u + 1 \le R\).

Hướng giải quyết

Chặt nhị phân

• Khoảng giá trị của kết quả: từ \(\min(A_i)\) đến \(\max(A_i)\).
• Với mỗi giá trị \(x\) được chọn, ta thực hiện hàm check(x).

Hàm kiểm tra check(x)

Ta cần tìm cặp \((u, v)\) sao cho:

1. \(L \le v - u + 1 \le R \Leftrightarrow v - R \le u - 1 \le v - L\).
2. \(P_v - P_{u-1} \ge 0 \Leftrightarrow P_v \ge P_{u-1}\).

Với mỗi vị trí \(v\) chạy từ \(L\) đến \(N\), ta cần tìm giá trị nhỏ nhất của \(P_{u-1}\) trong cửa sổ trượt \([v-R, v-L]\). Nếu \(P_v - \min(P_{u-1}) \ge 0\), thì giá trị \(x\) là khả thi.

Để tìm giá trị nhỏ nhất trong cửa sổ trượt hiệu quả, ta sử dụng Hàng đợi hai đầu (Deque). Deque sẽ lưu trữ các chỉ số \(j\) sao cho \(P_j\) tăng dần, giúp ta lấy được giá trị nhỏ nhất ở đầu hàng đợi trong thời gian \(O(1)\).

Các bước thực hiện

1. Chặt nhị phân giá trị \(x\) trong khoảng \([-10^9, 10^9]\).
2. Trong mỗi bước chặt nhị phân:
   • Tạo mảng \(P\) với \(P_i = P_{i-1} + (A_i - x)\).
   • Sử dụng Deque để duy trì giá trị nhỏ nhất của \(P_j\) trong khoảng \(j \in [i-R, i-L]\).
   • Nếu tìm thấy \(P_i - P_{dq.front()} \ge 0\), trả về true.
3. Sau khoảng 60-100 lần lặp chặt nhị phân, ta sẽ đạt được độ chính xác cần thiết.

Độ phức tạp

• Thời gian: \(O(N \cdot \log(\frac{max\_val - min\_val}{\epsilon}))\), với \(N = 10^6\) và số lần lặp chặt nhị phân khoảng 60-100, thuật toán chạy kịp trong giới hạn thời gian.
• Bộ nhớ: \(O(N)\) để lưu trữ mảng \(A\) và mảng tiền tố \(P\).

Code tham khảo

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

typedef long long ll;
const int MAXN = 1000005;
int n, L, R;
ll a[MAXN];
double pre[MAXN];

// Hàm kiểm tra xem có tồn tại đoạn con độ dài [L, R] có trung bình cộng >= x không
bool check(double x) {
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (a[i] - x);
    }

    deque<int> dq;
    for (int i = L; i <= n; i++) {
        // Cửa sổ cho u-1 là [i-R, i-L]
        // Thêm phần tử mới i-L vào deque
        int val_to_add = i - L;
        while (!dq.empty() && pre[dq.back()] > pre[val_to_add]) {
            dq.pop_back();
        }
        dq.push_back(val_to_add);

        // Loại bỏ phần tử ra khỏi cửa sổ [i-R, i-L]
        if (!dq.empty() && dq.front() < i - R) {
            dq.pop_front();
        }

        // Kiểm tra điều kiện tổng đoạn con >= 0
        if (!dq.empty() && pre[i] - pre[dq.front()] >= -1e-9) {
            return true;
        }
    }
    return false;
}

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

    if (!(cin >> n >> L >> R)) return 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    double l = -1e9, r = 1e9, ans = l;
    // Chặt nhị phân 100 lần để đảm bảo độ chính xác 4 chữ số thập phân
    for (int iter = 0; iter < 100; iter++) {
        double mid = (l + r) / 2.0;
        if (check(mid)) {
            ans = mid;
            l = mid;
        } else {
            r = mid;
        }
    }

    cout << fixed << setprecision(4) << ans << endl;

    return 0;
}