Матч 382, Непрерывная последовательность (ContiguousSubsequences)

Дивизион 2, Уровень 1

В заданной последовательности a₀, a₁, …, a_n-1 найти такую подпоследовательность рядом стоящих элементов a_i, a_i+1, …, a_j, что:

1. Длина подпоследовательности не меньше k;

2. Среднее значение подпоследовательности (a_i + a_i+1 + … + a_j) / (j – i + 1) наибольшее.

По заданному массиву а и значению k вернуть массив из двух элементов: i и j (начальный и конечный индексы искомой подпоследовательности). Если существует несколько искомых подпоследовательностей, то вернуть самую длинную. Если и таких подпоследовательностей будет несколько, то вернуть ту, которая имеет меньший начальный индекс.

Класс: ContiguousSubsequences

Метод: vector<int> findMaxAverage(vector<int> a, int k)

Ограничения: a содержит от 1 до 50 элементов, 1 £ a[i] £ 1000000, 1 £ k £ n, где n – количество элементов в а.

Вход. Массив чисел a и значение k.

Выход. Массив из двух элементов: i и j.

Пример входа

a	k
{1,3,7}	2
{5,1,3,4}	2
{1, 3, 2, 1, 1, 2, 2, 2, 2}	3

Пример выхода

{1, 2}

{2, 3}

{5, 8}

РЕШЕНИЕ

обработка массива

Вычисляем средние значения всех подпоследовательностей длины не меньше k и ищем среди них наибольшее. Сохраняем индексы начала и конца искомой подпоследовательности в массиве res.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class ContiguousSubsequences

{

public:

vector<int> findMaxAverage(vector<int> a, int k)

{

int i, j, n = a.size();

vector<int> s(n+1), res(2,0);

double max = 0;

for(s[0] = i = 0; i < a.size(); i++) s[i+1] = s[i] + a[i];

for(i = 0; i < n; i++)

for(j = i + k - 1; j < n; j++) // interval [i..j], summa = s[j+1] - s[i]

{

if ((s[j+1] - s[i] > max * (j - i + 1)) ||

((s[j+1] - s[i] == max * ( j - i + 1)) &&

(j - i > res[1] - res[0])))

{

max = (1.0 * s[j+1] - s[i]) / (j - i + 1);

res[0] = i; res[1] = j;

}

}

return res;

}

};