37
правок
Изменения
Нет описания правки
===Псевдокод===
====Алгоритм 1====
<tex> S \leftarrow \{1 \ldots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex>
<tex> \mathtt{time++}</tex>
====Алгоритм 2====
Этот алгоритм реализован с помощью [[Двоичная_куча|двоичной кучи]] <tex>\mathtt{Heap}</tex> в которой операции вставки и извлечения выполняются за <tex>O(\log n)</tex>, а операция поиска максимального элемента за <tex>O(1)</tex>
<tex> S \leftarrow \{1 \ldots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
<tex> \mathtt{answer} \leftarrow 0</tex>
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''
Heap.insert(<tex>w_i</tex>)
'''while''' <tex> S \neq \varnothing </tex>
<tex> j \leftarrow null </tex>
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant </tex> Heap.Max()
<tex> j \leftarrow i </tex>
'''if''' <tex>j \neq null </tex>
<tex> S \leftarrow S \setminus j</tex>
Heap.extractMax()
<tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex>
<tex> \mathtt{time++}</tex>
В начале алгоритма мы добавляем все элементы <tex>w_i</tex> в двоичную кучу тратя на это <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n)</tex> что равно <tex>O(n \log n)</tex> времени.
===Сложность алгоритма===
