Техника скользящего окна
Узнайте о технике скользящего окна
Введение
Предположим, нам дан массив и число . Мы хотим найти подмассив длины с максимальным средним значением.
Узнайте о технике скользящего окна
Предположим, нам дан массив и число . Мы хотим найти подмассив длины с максимальным средним значением.
Поскольку все подмассивы должны иметь одинаковую длину, это эквивалентно поиску подмассива длины с максимальной суммой.
Простое решение — проверить каждый подмассив длины и вычислить его среднее независимо.
Это работает за время , потому что для каждой начальной позиции мы пересчитываем всю сумму с нуля.
Можно сделать лучше.
Вместо пересчёта суммы для каждого подмассива мы храним сумму текущего отрезка длины и обновляем её, когда отрезок сдвигается на один шаг вправо.
Мы называем текущий отрезок окном.
Если мы уже знаем сумму текущего окна, то после сдвига на один шаг вправо:
Так что новую сумму можно обновить за константное время.
Сначала вычислите сумму первого окна .
Затем для каждой следующей позиции сдвигайте окно на один шаг вправо:
Иными словами, при переходе к окну, заканчивающемуся в позиции , сумма изменяется на:
Среднее значение текущего окна просто равно:
Пусть
Окна:
Итак, максимальное среднее получается у подмассива .
for (int i = 1; i + k - 1 <= n; i++) {
double sum = 0;
for (int j = 0; j < k; j++) {
sum += a[i + j];
}
sum /= k;
res = max(res, sum);
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<double> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
double sum = 0;
for (int i = 1; i <= k; i++) {
sum += a[i];
}
double res = sum / k;
for (int i = k + 1; i <= n; i++) {
sum += a[i] - a[i - k];
res = max(res, sum / k);
}
cout << fixed << setprecision(10) << res << "\n";
return 0;
}