Изменения
Нет описания правки
<tex>t_1 \leftarrow r_1 </tex>
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex>
Этот алгоритм работает за <tex>O(n \log n +n)</tex>
====Реализация 2====
Перед началом алгоритма [[Сортировка|отсортируем]] работы по порядку невозрастания веса.Функция minFreeTime за <tex>O(\log n)</tex> ищем минимальное свободное время на заданном промежуткенеубывания времени появления.
<tex> S \leftarrow \{1 \ldots n\}</tex> <tex> \mathtt{time} \leftarrow 0r_1</tex>
<tex> \mathtt{answer} \leftarrow 0</tex>
<tex> \mathtt{count} \leftarrow 0</tex>
'''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''
'''if''' <tex> \mathtt{time} \leqslant r_{i}tail = r_i</tex> <tex> \mathtt{time} \leftarrow r_{imas}</tex> <tex> j \leftarrow null </tex> <tex> j \leftarrow </tex> minFreeTime(<tex>r_{[i} \ldots \mathtt{time}</tex>) '''if''' <tex>j \neq null </tex> <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} ]+ j \cdot w_{i}</tex> '''if''' <tex>j = \mathtt{time} </tex> <tex> \mathtt{time++}</tex>
'''else'''
push(<tex>r_i</tex>) '''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do''' '''for''' <tex>j \leftarrow i </tex> '''to''' <tex>i + \mathtt{mas}[i]</tex> '''do''' insert[<tex>w_j</tex>] <tex>\mathtt{count} \leftarrow \mathtt{mas}[i]</tex> <tex>i \leftarrow i + \mathtt{mas}[i]</tex> <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \max\limits_{j \in S, j = 1 \ldots n} w_{j}</tex> <tex> S \leftarrow S \setminus j</tex> <tex> \mathtt{time++}</tex> '''for''' <tex>i\leftarrow 1 </tex> '''to''' <tex>\mathtt{count}</tex> '''do''' <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \max\limits_{j \in S, j = 1 \ldots n} w_{j}</tex> <tex> S \leftarrow S \setminus j</tex> <tex> \mathtt{time++}</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> времени.
