Торговля вином в Герговии - оптимизация
У меня есть задание , сижу несколько часов, набросал три варианта (с тремя , двумя и одним циклом), на небольшие входные данные задача решается быстро, но в условиях сказанно что N может быть равно 100.000 чисел,даже с 30 тысячами чисел, при одном цикле, вычисления идут 30 секунд, помогите разобраться, потому что я сижу над этой задачей уже довольно долго.
Необходимо, сделать чтобы можно было ввести 100.000 чисел до 10 секунд времени.
Все покупают вино у других жителей города. Каждый день каждый житель решает, сколько вина он хочет купить или продать. Интересно, что спрос и предложение всегда одинаковы, так что каждый житель получает то, что хочет. Однако есть одна проблема: транспортировка вина из одного дома в другой приводит к работе. Поскольку все вина одинаково хороши, жителям Герговии все равно, с кем они торгуют, их интересует только продажа или покупка определенного количества вина.
Транспортировка одной бутылки вина из одного дома в соседний дом приводит к одной единице работы
def wine_trade_V4(n,numList):
work = 0
for i in range(n):
for j in range(n):
if numList[i] > 0:
if numList[j] < 0:
idx = abs(numList.index(numList[j])-numList.index(numList[i]))
numList[j]+=numList[i]
work += numList[i] * idx
numList[i] = 0
if numList == [0]*n:
break
return work
Ответы (1 шт):
У меня вот такое получилось:
def solution(a):
result = 0
for i in range(1, len(a)):
a[i] += a[i-1]
result += abs(a[i-1])
return result
print(solution([5, -4, 1, -3, 1])) # 9
print(solution([-1000, -1000, -1000, 1000, 1000, 1000])) # 9000
Просто тащим бутылки (положительные и отрицательные) из дома в дом и считаем работу для этого необходимую(по модулю)
у меня не выходило, потому что я в range от 0 начинал, а не с 1.
Это не принципиально; вот вариант без мутации массива, с простым суммированием в переменную. Последняя сумма всё равно нулевая, по условию.
def solution(a):
work = 0 # всего проделано работы
total = 0 # бутылок сейчас в руках
for w in a:
total += w
work += abs(total)
return work