Префиксные суммы и скользящее окно
Префиксные суммы дают сумму любого отрезка последовательности одним вычитанием, без нового цикла по отрезку. Скользящее окно пересчитывает сумму участка при сдвиге: прибавляет число, которое вошло, и вычитает число, которое ушло. Префиксные и суффиксные максимумы позволяют выбрать несколько чисел с заданным разносом индексов за один проход, и на этих приёмах стоят быстрые программы для файла B в заданиях 24, 26 и 27.
Отрезки последовательности за один проход
Элементы последовательности нумеруют с нуля, как индексы списка в Python. Каждый из этих приёмов обходит список один раз, то есть работает за .
- Префиксная сумма: , . Сумма элементов с индексами от до равна .
- Сумма расстояний с весами считается по двум префиксным суммам: сумме весов и сумме произведений .
- Скользящее окно длины : при сдвиге на один элемент прибавьте вошедший элемент и вычтите ушедший .
- Префиксный максимум , суффиксный . Чтобы выбрать числа с разносом индексов, перебирайте одно число, а остальные берите из этих списков.
Префиксные суммы и сумма отрезка
Префиксная сумма — сумма первых элементов последовательности: , , и так далее. Весь список строят одним циклом: . В нём на один элемент больше, чем в последовательности.
Сумма элементов с индексами от до равна : из суммы первых элементов вычитаем сумму первых . Каждый такой запрос стоит одно вычитание, а не цикл по отрезку. Это нужно, когда отрезков много: перебор всех отрезков с циклом внутри работает за , с префиксными суммами — за , подробнее в теме сложность алгоритма.
Пример
Дана последовательность 3, −1, 4, 1, 5, 9, 2. Найдите сумму элементов с индексами от 2 до 5 по префиксным суммам.
- 1.Префиксные суммы: .
- 2.Индексы от 2 до 5: , .
- 3.. Проверка: . Программа печатает список и число 19.
Ответ:
Сумма расстояний с весами
В задачах о размещении склада нужна сумма : вес каждого пункта , умноженный на расстояние до точки . Модуль раскрывают отдельно слева и справа от . Для пунктов левее расстояние равно , и сумма равна . Для пунктов правее сумма равна .
Обе суммы на любом отрезке дают две префиксные суммы: — по весам , — по произведениям . Тогда стоимость для каждого считается за несколько действий, а не циклом по всем пунктам. Как составить саму стоимость, разобрано в теме целевая функция.
Пример
Пункты с номерами 0, 1, 2, 3, 4 стоят на прямой через 1 км, их веса 2, 1, 3, 1, 2. Найдите по префиксным суммам.
- 1.; .
- 2.Слева от пункты 0 и 1: .
- 3.Справа пункты от 2 до 4: .
- 4.Сумма . Проверка: . Программа печатает 5 5 10.
Ответ:
Кольцо: утроенный список
На кольцевой трассе из пунктов расстояние между пунктами и равно , где : можно ехать в любую сторону. От пункта вперёд по кольцу ближе лежат пунктов, назад — пунктов. Вместе с самим это все пунктов, каждый один раз.
Чтобы не считать индексы по модулю , список весов повторяют три раза: w * 3. Центр берут в средней копии, от до . Тогда пункты от до лежат подряд, и стоимость считается по сумме расстояний с весами. Программа ниже читает файл и печатает минимум за .
f = open('27_A.txt')n = int(f.readline())w = [int(f.readline()) for i in range(n)] * 3a = n // 2b = n - 1 - ap1 = [0] * (3 * n + 1)p2 = [0] * (3 * n + 1)for t in range(3 * n): p1[t + 1] = p1[t] + w[t] p2[t + 1] = p2[t] + t * w[t]best = Nonefor m in range(n, 2 * n): right = (p2[m + a + 1] - p2[m]) - m * (p1[m + a + 1] - p1[m]) left = m * (p1[m] - p1[m - b]) - (p2[m] - p2[m - b]) if best is None or left + right < best: best = left + rightprint(best)
Пример задания
Открытый банк ФИПИ
Для участников велогонки на каждом километре кольцевой трассыс двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N километров. Нулевой и N-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплектыпитания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна. Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.
Входные данные:
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов питания на кольцевой трассе. В каждой из следующих N строк находится число – количество комплектов питания на пункте (все числа натуральные, количество комплектов питания на каждом пункте не превышает 1000). Числа указаны в порядке расположения пунктов питания спортсменов на трассе, начиная с первого километра. В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле:
6
8
20
5
13
7
19
При таких исходных данных, если пункты питания установлены на каждом километре трассы, необходимо открыть мобильный цех подготовки комплектов питания для спортсменов в пункте 6. В этом случае сумма транспортных затрат составит:
1 ∙ 7 + 0 ∙ 19 + 1 ∙ 8 + 2 ∙ 20 + 3 ∙ 5 + 2 ∙ 13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долг.
Скользящее окно постоянной длины
Скользящее окно — участок из соседних элементов, который сдвигают по последовательности на один элемент. Сумму первого окна считают циклом. При сдвиге в окно входит элемент , а уходит , поэтому новая сумма равна старой плюс минус . Так же пересчитывают число чётных элементов в окне или число нужных символов: прибавляют вклад вошедшего и вычитают вклад ушедшего.
Если в последовательности есть отрицательные числа, начальный максимум берут из первого окна, а не 0: иначе ответ может оказаться больше любой настоящей суммы.
Пример
Дана последовательность 4, −2, 7, 1, −5, 6, 3. Найдите наибольшую сумму трёх соседних элементов.
- 1.Первое окно: .
- 2.Сдвиг: входит 1, уходит 4, сумма .
- 3.Дальше: , , .
- 4.Наибольшая из сумм 9, 6, 3, 2, 4 — первая. Программа печатает 9.
Ответ:
Окно из k вхождений символа
Самый длинный участок строки, в котором символ встречается ровно раз, ищут окном из соседних позиций этого символа: ровно K вхождений.
Префиксный и суффиксный максимум
Префиксный максимум — наибольший из элементов , суффиксный максимум — наибольший из . Список строят проходом слева направо: . Список — проходом справа налево: .
Нужно выбрать три числа так, чтобы индексы соседних отличались не меньше чем на , а сумма была наибольшей. Перебирайте среднее число . Левое число лучше всего взять наибольшим среди индексов от 0 до включительно, это . Правое — наибольшим среди индексов от до конца, это . Ответ — наибольшая сумма по всем от до .
f = open('27_A.txt')k = int(f.readline())n = int(f.readline())a = [int(f.readline()) for i in range(n)]left = [0] * nleft[0] = a[0]for i in range(1, n): left[i] = max(left[i - 1], a[i])right = [0] * nright[n - 1] = a[n - 1]for i in range(n - 2, -1, -1): right[i] = max(right[i + 1], a[i])best = Nonefor j in range(k, n - k): s = left[j - k] + a[j] + right[j + k] if best is None or s > best: best = sprint(best)
Пример задания
Открытый банк ФИПИ
По каналу связи передаётся последовательность целых чисел – показания прибора. В течение N мин. (N – натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической
сети и передаёт его на сервер.
Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K мин., а сумма этих трёх чисел была максимально возможной. Запишите в ответе найденную сумму.
Входные данные:
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число K – минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй –количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих N строк находится одно целое число, по модулю не превышающее 10 000 000, которое обозначает значение напряжения в соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле:
2
6
150
–150
20
–200
–300
0
При таких исходных данных искомая величина равна 170 – это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.