1

Всем здравствуйте! Есть код для решения задачи, но он не проходит по времени.

Условие:
Фирма 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), но я не знаю, как можно это реализовать. Помогите, пожалуйста. Заранее спасибо!

1 ответ 1

2

Про кучу - верно, и описание её же есть в хелпе.

import heapq
a = [10, 11, 12, 13]
heapq.heapify(a)
sm = 0
for i in range(len(a)-1):
    x = heapq.heappop(a)
    y = heapq.heappop(a)
    s = x + y
    sm += s*0.05
    heapq.heappush(a, s)
print(sm)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.