Обработка массива по условию

Обработка массива по условию — это последовательный просмотр его элементов и выполнение действия только для тех элементов, которые удовлетворяют заданному условию. Один и тот же приём помогает считать подходящие элементы, находить их сумму, максимум или первый элемент с нужным свойством.

Общий шаблон обработки

Пусть дан массив \(a\) из \(n\) элементов. Для каждого индекса \(i\) проверяем условие, записанное через \(a[i]\). Если условие истинно, выполняем нужное действие: увеличиваем счётчик, добавляем элемент к сумме, сравниваем его с текущим максимумом или сохраняем его индекс.

В задачах на экзамене особенно важно различать индекс и значение элемента. \(i\) — это номер позиции, а \(a[i]\) — число, записанное в этой позиции. Если требуется вывести сами элементы, используем \(a[i]\); если нужно найти позицию, сохраняем $i.

for i in range(n):
    if condition(a[i]):
        action(a[i], i)

Подсчёт и суммирование

Для подсчёта подходящих элементов используется переменная-счётчик. Перед циклом её обязательно обнуляют. Каждый раз, когда условие истинно, счётчик увеличивается на единицу. Подробный шаблон можно повторить после изучения условного счётчика.

Здесь \([P]\) — индикатор условия: он равен \(1\), если условие истинно, и \(0\) в противном случае. В программе обычно используют if, а не записывают индикатор явно.

count = 0
for x in a:
    if x % 3 == 0:
        count += 1

Для суммы начальное значение равно нулю. Подходящий элемент прибавляется к сумме. Такой алгоритм является частным случаем условной суммы. Если условных элементов нет, результат останется равным нулю — это корректный ответ, если отдельно не сказано обратное.

Например, для суммы положительных элементов условие \(a[i]>0\), а для суммы элементов на отрезке \([L,R]\) условие имеет вид \(L\le a[i]\le R\). При двух границах важно проверить обе части условия.

Поиск элемента и его позиции

Если требуется найти первый элемент, удовлетворяющий условию, удобно просматривать массив слева направо и завершить цикл сразу после нахождения. Для обозначения того, что элемент ещё не найден, используют специальное значение, например -1 для индекса.

index = -1
for i in range(n):
    if a[i] > 100:
        index = i
        break

После цикла проверяют index. Если он равен -1, подходящего элемента нет. Иначе первый подходящий элемент равен a[index]. Для поиска последнего подходящего элемента break не используют: индекс перезаписывается при каждом совпадении.

Если заранее известно, что хотя бы один элемент подходит, максимум можно начать с очень маленького числа. Надёжнее найти первый подходящий элемент и взять его за начальный максимум, а затем продолжить просмотр с оставшейся части массива. Аналогично ищется минимум.

Проверка существования особенно важна: максимум пустого множества не определён. Поэтому в программе часто хранят флаг found или индекс первого подходящего элемента.

Разобранный пример: сумма и количество

Дан массив \([12,-5,7,0,18,-2,9]\). Требуется определить количество положительных нечётных элементов и их сумму. Условие должно одновременно проверять знак и нечётность: \(x>0\) и \(x\bmod 2\ne0\).

a = [12, -5, 7, 0, 18, -2, 9]
count = 0
s = 0
for x in a:
    if x > 0 and x % 2 != 0:
        count += 1
        s += x
print(count, s)

Границы, отрезки и несколько условий

Условие «элемент находится на отрезке \([L,R]\)» означает включение обеих границ: \(L\le a[i]\le R\). Если границы не входят в отрезок, используют строгие неравенства: \(L<a[i]<R\). Соседняя тема количество элементов на отрезке помогает закрепить этот шаблон.

Если нужно обработать элементы на позициях от \(l\) до \(r\), ограничивают сам цикл индексами. При нумерации с нуля в Python правая граница диапазона не включается: range(l, r + 1) обрабатывает позиции \(l, l+1,\ldots,r\).

Для каждого элемента условие проверяют ровно один раз, поэтому время работы обычно равно \(O(n)\), а дополнительная память — \(O(1)\). Если требуется много запросов к отрезкам, может понадобиться сумма на отрезке с префиксными суммами.

Как выбирать шаблон

Произведение инициализируют единицей, а не нулём, иначе итог всегда будет равен нулю. Перед применением шаблона уточните: что именно нужно вывести — значение, индекс, количество или агрегатную характеристику. Для произведения элементов массива полезна страница произведение элементов массива.