Всем здравствуйте! Есть код для решения задачи, но он не проходит по времени.
Условие:
Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму 𝑁
натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10
, 11
, 12
и 13
. Тогда если мы сначала сложим 10
и 11
(это обойдется нам в 1.05$), потом результат с 12
(1.65$), и затем с 13
(2.3$), то всего мы заплатим 5$. А если же сначала отдельно сложить 10
и 11
(1.05$), потом 12
и 13
(1.25$) и, наконец, сложить между собой два полученных числа (2.3$), то в итоге мы заплатим лишь 4.6$.
Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных 𝑁
чисел.
Входные данные:
Первая строка входных данных содержит число 𝑁
(2
≤ 𝑁
≤ 10**5
). Во второй строке заданы 𝑁
натуральных чисел, каждое из которых не превосходит 10000
.
Выходные данные:
Определите, сколько денег нам потребуется на нахождения суммы этих 𝑁
чисел. Результат должен быть выведен с двумя знаками после десятичной точки.
Примеры:
Вход 1:
4
10 11 12 13
Выход 1:
4.60
Вход 2:
2
1 1
Выход 2:
0.10
Мой код:
from bisect import *
from collections import deque
k = int(input())
B = sorted([int(_) for _ in input().split()])
A = deque()
A.extend(B)
cost = 0
while len(A) != 1:
sum = A[0] + A[1]
for _ in range(2): A.popleft()
idx = bisect(A, sum)
A.insert(idx, sum)
cost += sum * 0.05
print(cost)
print(A)
print('%.2f'%cost)
Возможно, для ускорения работы, здесь нужно применить кучу (heap), но я не знаю, как можно это реализовать. Помогите, пожалуйста. Заранее спасибо!