Изменения

Перейти к: навигация, поиск

1ripi1sumwc

471 байт убрано, 22:09, 9 июня 2015
Нет описания правки
<tex> S \leftarrow \{1 \ldots n\}</tex>
<tex> \mathtt{time} \leftarrow r_10</tex>
<tex> \mathtt{answer} \leftarrow 0</tex>
<tex> \mathtt{count} j \leftarrow 01</tex> '''forwhile''' <tex>i S \neq \leftarrow 1 varnothing </tex> '''tofor''' <tex>ni = j</tex> '''do''' '''ifto''' <tex>tail = r_in</tex> <tex>\mathtt{mas}[i]++</tex> '''elsedo''' push(<tex>r_i</tex>) '''forif''' <tex>i r_i \leqslant \leftarrow 1 mathtt{time}</tex> '''to''' insert(<tex>nw_i</tex> ) '''doelse''' '''for''' <tex>j \leftarrow = i </tex> '''tobreak''' <tex>i + \mathtt{mas}[i]</tex> '''do''' insert[<tex>w_j</tex>] <tex>\mathtt{count} k \leftarrow \mathtt{mas}[i]null</tex> <tex>i k \leftarrow i + \mathtt{mas}[i]</tex> <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \max\limits_{j \in S, j h = 1 ,\ldots n,j} w_{jh}</tex> <tex> S \leftarrow S \setminus j</tex> <tex> \mathtt{time++}</tex> '''for''' <tex>i \leftarrow 1 </tex> '''toif''' <tex>k \mathtt{count}neq null</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 jk</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> времени.
Анонимный участник

Навигация