Задание №27 — Оптимальный алгоритм для большого количества данных

#69815Задание №27ФИПИ

Анализ данных

По каналу связи передаётся последовательность целых чисел – показания прибора. В течение 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

29924_27_A.txt

29924_27_B.txt

Правильный ответ

189536 17210

Пояснение

Решение:

Нужно выбрать три показания с номерами минут $i \lt j \lt l$ так, чтобы $j - i \ge K$ и $l - j \ge K$ , а сумма $a_i + a_j + a_l$ была наибольшей. Перебор всех троек — это $O(N^3)$ , для файла B с сотнями тысяч показаний он не закончится никогда, поэтому нужен линейный алгоритм.

Идея: зафиксируем среднее из трёх чисел. Если средним выбрано показание с номером $j$ , то левое число можно брать любое с номером не больше $j-K$ , а правое — любое с номером не меньше $j+K$ . Обе части независимы, поэтому выгоднее всего взять максимум на левом префиксе и максимум на правом суффиксе. Оба массива максимумов считаются заранее одним проходом:

pref[i] — наибольшее из показаний с номерами от 0 до i;
suf[i] — наибольшее из показаний с номерами от i до конца.

После этого остаётся один проход по возможным средним элементам, и весь алгоритм работает за $O(N)$ . Обратите внимание: показания бывают отрицательными, поэтому начальное значение ответа нужно брать заведомо маленьким, а не нулём.

def solve(name):
    f = open(name)
    k = int(f.readline())
    n = int(f.readline())
    a = [int(f.readline()) for i in range(n)]

    pref = [0] * n
    pref[0] = a[0]
    for i in range(1, n):
        pref[i] = max(pref[i - 1], a[i])

    suf = [0] * n
    suf[n - 1] = a[n - 1]
    for i in range(n - 2, -1, -1):
        suf[i] = max(suf[i + 1], a[i])

    best = -10**18
    for j in range(k, n - k):
        best = max(best, pref[j - k] + a[j] + suf[j + k])
    print(best)

solve('27_A.txt')
solve('27_B.txt')

На типовом примере из условия программа выдаёт 170 — значит, она реализует именно требуемое правило. Для файла A получаем 189536, для файла B — 17210. Ответ: 189536 17210