Для этого можно использовать минимальную кучу:
Алгоритм
- Сортировать входные данные по t i
- Создать пустую минимальную кучу, которая будет содержать v i , которые сохраняются
- Итерация отсортированного ввода. Для каждого i :
- Если t i <размер кучи, то это означает, что этот элемент не может быть сохранен, если другой, ранее не выбранный Стихия Убедитесь, что минимальное значение в куче меньше <em>v i . Если это так, тогда будет выгодно взять это минимальное значение из кучи и поместить вместо него v i .
- В противном случае просто добавьте v i в кучу.
- В любом случае обновляйте общее значение кучи
- Возвращает общее значение куча
Почему это работает
Это работает, потому что на каждой итерации мы имеем этот инвариант :
Размер кучи представляет две вещи одновременно. Это и:
- Количество элементов, которые мы по-прежнему считаем возможными кандидатами для окончательного решения, и
- Количество прошедших недель.
Идея состоит в том, что каждому элементу в куче назначается одна неделя, и поэтому нам нужно столько же недель, сколько есть элементов в куче.
Итак, на каждой итерации мы пытаемся выполнить 1 неделя. Однако, если следующий посещенный элемент может быть разрешен только в прошедшем периоде (т.е. его последняя возможная неделя - это неделя, которая уже прошла пройдено ), то мы не можем просто так добавить его в куча, так как для нее нет доступной недели. Вместо этого мы проверяем, будет ли рассматриваемый элемент лучше заменяться на элемент, который мы уже выбрали (и находится в куче). Если мы обменяем его, тот, который проиграл, не сможет остаться в куче, потому что теперь у нас нет доступной недели для , чем один (помните, что ее временное ограничение еще более строгое - мы посещаем их в порядке сроков). Так что, будем мы обмениваться или нет, размер кучи останется неизменным.
Во-вторых, куча должна быть кучей, потому что нам нужен эффективный способ всегда знать, какой элемент имеет значение наименьшее . В противном случае, если бы это был простой список, нам пришлось бы сканировать этот список на каждой итерации, чтобы сравнить его значение с тем, с которым мы имеем дело в настоящее время (и хотим потенциально обмениваться). Очевидно, что обмен выгоден только в том случае, если общая стоимость кучи увеличивается. Поэтому нам нужен эффективный способ быстрого нахождения значения bad . Мин-куча обеспечивает это.
Реализация
Вот реализация в Python:
from collections import namedtuple
from heapq import heappush, heapreplace
Node = namedtuple("Node", "time,value")
def kepler(times, values):
n = len(values)
# Combine corresponding times and values
nodes = [Node(times[i], values[i]) for i in range(n)];
nodes.sort() # by time
totalValue = 0
minheap = []
for node in nodes:
if node.time < len(minheap): # Cannot be visited in time
leastValue = minheap[0] # See if we should replace
if leastValue < node.value:
heapreplace(minheap, node.value) # pop and insert
totalValue += node.value - leastValue
else:
totalValue += node.value
heappush(minheap, node.value)
return totalValue
И вот пример ввода для нее:
times = [3,3,0,2,6,2,2]
values =[7,6,3,2,1,4,5]
value = kepler(times, values)
print(value) # 23
Сложность времени
Сортировка будет представлять O (nlogn) сложность времени. Несмотря на то, что можно рассмотреть некоторую радикальную сортировку, чтобы уменьшить это значение до O (n) , использование кучи также представляет собой наихудший случай O (nlogn) . Таким образом, алгоритм имеет временную сложность O (nlogn) .