11721. Сумма подмассивов 1

Дан массив из n положительных целых чисел. Найдите количество подмассивов, сумма которых равна x.

Вход. Первая строка содержит размер массива n (1 ≤ n ≤ 2 * 10⁵) и заданную сумму x (1 ≤ x ≤ 10⁹). Следующая строка содержит n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) – элементы массива.

Выход. Выведите требуемое количество подмассивов.

Пример входа	Пример выхода
5 7 2 4 1 2 7	3

РЕШЕНИЕ

два указателя

Анализ алгоритма

Реализуем скользящее окно с помощью двух указателей i и j. Для каждого фиксированного i = 1, 2, … будем по максимуму раздвигать интервал [i … j] так, чтобы сумма элементов на нем была не больше x. То есть для каждого i ищем такое наибольшее значение j, что сумма элементов на интервале [i … j] не превышает x, а сумма элементов на интервале [i … j + 1] уже больше x.

Пусть s – сумма чисел на интервале [i … j]. Если s + a[j + 1] ≤ m, то расширяем интервал до [i … j + 1]. Иначе сокращаем его до [i + 1 … j]. Подсчитываем количество интервалов с суммой x.

Пример

Рассмотрим движение указателей для приведенного примера.

1. i = 0, j движется вперед, пока сумма чисел на интервале [i … j] не станет больше x = 7. Остановимся на интервале [0 … 2], так как сумма чисел на нем равна 7, а на интервале [0 … 3] сумма чисел уже равна 9.

2. i = 1, j двигаем вперед до 3. Сумма чисел на интервале [1 … 3] равна 7, а на интервале [1 … 4] уже 14.

3. i = 2, рассматриваемый интервал [2 … 3]. Сумма чисел на нем равна 3, однако двигать индекс j вперед мы не можем, потому что сумма чисел на интервале [2 … 4] равна 10, что больше x = 7.

4. i = 3, рассматриваемый интервал [3 … 3]. Сумма чисел на нем равна 2, однако двигать индекс j вперед мы не можем, потому что сумма чисел на интервале [3 … 4] равна 9, что больше x = 7.

5. i = 4, рассматриваемый интервал [4 … 4]. Сумма чисел на нем равна 7.

Количество подмассивов с суммой x = 7 равно 3. Они начинаются с индексов 0, 1 и 4.

Реализация алгоритма

Объявим рабочий массив.

#define MAX 200001

long long a[MAX];

Читаем входные данные.

scanf("%d %lld", &n, &x);

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

scanf("%lld", &a[i]);

Изначально установим текущий интервал [i … j] = [0; 0]. Сумма чисел на этом интервале равна s = 0.

s = j = 0;

Для каждого значения i последовательно обрабатываем интервалы [i … j].

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

{

Для фиксированного левого конца i интервала [i … j] ищем наибольшее j, для которого сумма элементов на указанном интервале не превосходит x.

while ((j < n) && (s + a[j] <= x)) s += a[j++];

Если сумма чисел s на текущем интервале [i … j] равна x, то искомое количество подмассивов cnt увеличиваем на 1.

if (s == x) cnt++;

Пересчитываем сумму чисел s для интервала [i + 1 … j].

s -= a[i];

}

Выводим ответ.

printf("%lld\n", cnt);