Бинпоиск по ответу с вещественным предикатом: задача про максимальное среднее подотрезка

Это бинпоиск по вещественному ответу x = «среднее». Предикат: check(x) = «существует ли подотрезок длины >= L со средним >= x». Монотонность: если такой подотрезок есть для среднего x, то и для любого меньшего x' < x он тоже годится (то же среднее >= x > x'). Значит предикат true...true false...false по x — ищем максимальный истинный x.

Ключ — как проверять check(x). Среднее подотрезка >= x ⇔ (сумма)/(длина) >= x ⇔ сумма(a[i]) - x*длина >= 0 ⇔ сумма по подотрезку из b[i] = a[i] - x неотрицательна. Значит вопрос сводится к: «есть ли в массиве b подотрезок длины >= L с суммой >= 0».

Это решается за O(n) через префиксные суммы pref массива b и минимум префикса с отставанием L: для каждого r (r >= L) проверяем pref[r] - min(pref[0..r-L]) >= 0. Минимум поддерживаем на лету.

bool check(const vector<double>& a, int L, double x) {
    int n = a.size();
    vector<double> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + (a[i] - x);
    double minPref = 0; // min(pref[0..r-L])
    for (int r = L; r <= n; r++) {
        minPref = min(minPref, pref[r - L]);
        if (pref[r] - minPref >= 0) return true;
    }
    return false;
}

Внешний бинпоиск — по числу итераций (100 штук) в [minA, maxA]. Общая сложность O(n * iters) ≈ O(100 n), память O(n). Это классический трюк «бинпоиск по дробному ответу + сведение к сумме через вычитание кандидата».