Оптимизировать задачу на Python

Question

n, m = map(int, input().split())

costs = [int(x) for x in input().split()]

maxem = 0

for i in range(1, m + 1):
    left = i
    for c in costs:
        if left - c >= 0:
            left = left - c
    maxem = max(maxem, left)

print(maxem)

Вот код. Есть список некоторых чисел, по которым последовательно проходимся. И есть число, от которого нужно отнимать элементы этого списка. Число от 0 до m. Если элемент списка больше числа, просто его пропускаем. Нужно выбрать такое число из отрезка от 0 до m, чтобы после прохождения всего списка осталось наибольшее возможное значение.

Допустим список 5 4 1. Максимальное 10. Если возьмем 10, можно отнять и 5, и 4, и 1. Останется 0. Например, возьмем 8, сможем отнять 5, не сможем 4 и сможем 1. В конце останется 2. Это и будет максимальным.

Сделал втупую перебором, как это можно оптимизировать?

Answer 1

Работайте сразу с интервалом возможных остатков от суммы [low, high]. Первоначально low = 1, high = m.

В цикле "вычитаем" из интервала число c:

если c ≤ low, то новый интервал [low - c, high - c].
если low < c ≤ high, то новый интервал [0, max(c - 1, high - с)].

Числа из [low, c - 1] не меняются. Числа из [c, high] уменьшаются на c, что даёт [0, high - c]. Нам нужно объединение [low, c - 1] ⋃ [0, high - c], поэтому такой новый интервал. Здесь используется что low ≤ 1, иначе множество значений может стать не одним интервалом и задача усложнится.
если high < c, интервал не меняется.

Получится такой код:

_, m = map(int, input().split())

low = 1
high = m

for c in map(int, input().split()):
    if c <= low:
        low -= c
        high -= c
    elif c <= high:
        low = c
        high = max(c - 1, high - c)
print(high)

БЛОГ НА HUSL

Оптимизировать задачу на Python

Ответы (1 шт):