Задача, которую я должен выполнить, — взять массив определенной длины и выяснить, какой подсписок имеет наиболее близкую сумму к другому заданному числу. Затем мне нужно распечатать индекс этого подмассива.
Для всех, кто не понимает эту проблему, мы складываем индексы данного списка, и в тот момент, когда их сумма превышает или равна требуемому количеству мощности (второе число во второй строке ввода), мы добавляем его в другой список, а затем мы добавляем индекс числа, с которого мы начали отсчет, и индекс числа, которое мы перестали добавлять, в третий список. После этого мы начинаем со следующего индекса. Например, в этом вводе, если мы начнем отсчет с индекса списка 0, мы увидим, что если мы продолжаем складывать до индекса 6, сумма будет 28. Мы продолжаем повторять это, но на этот раз с индекса 1, затем 2, 3, 4 и т. Д. Когда мы закончим, мы поймем, что числа с наиболее близкой суммой к 23 — это числа 7, 8, 9, которые варьируются от 6 до 8 и имеют сумму 24. Итак, мы печатаем: 6 8.
И если кому-то интересно, если мы получим несколько диапазонов, соответствующих критериям, мы выберем, в соответствии с постановкой задачи, ближайший к входу, тот, у которого самый низкий начальный индекс и самый низкий конечный индекс. В нашем случае мы позаботились об этом, потому что каждый раз, когда мы добавляем сумму индексов в server_lst мы добавляем их индексы одновременно в index_lst. Итак, индексы, которые печатаются, являются первыми с наилучшей суммой.
num_of_cases = int(input())
for case in range(num_of_cases):
num_of_servers, c_power = map(int, input().split())
server_lst = list(map(int, input().split()))
server_total = []
server_index = []
j = 0
total = 0
k = 0
def servers(lst, k):
global total
global j
for i in range(k, len(lst)):
if total < c_power:
total += lst[i]
j += 1
else:
server_total.append(total)
j += k
server_index.append([k, j-1])
j = 0
total = 0
break
def execute(server_lst, k):
for i in range(len(server_lst)):
k = i
servers(server_lst, k)
min_pow = min(server_total)
winner = server_total.index(min_pow)
mf = server_index[winner]
print('Case #{}:'.format(case+1), *mf )
execute(server_lst, k)
Проблема, с которой я сейчас сталкиваюсь, заключается в том, что, хотя он работает, для запуска входных данных размером 10 МБ требуется около 10 минут. Можно ли как-нибудь улучшить его, чтобы он работал быстрее?
Вот очень простой ввод:
1
10 23
1 2 3 4 5 6 7 8 9 10
и вывод на это:
Case #1: 6 8
Ограничения:
- 1 ≤ num_of_cases ≤ 20.
- 1 ≤ серверов ≤ 100 000.
- 1 ≤ количество необходимой мощности (c_power) ≤ 10000000000.
- 1 ≤ мощность каждого сервера (каждый индекс в server_lst) ≤ 1 000 000, для i = 0… N — 1
Заранее спасибо.