Изменения

Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\fracdfrac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание, время работы будет <tex>O(n)</tex>.

Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i nw_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Вес работ Данный алгоритм корректен по [[СортировкаЗадача_о_минимуме/максимуме_скалярного_произведения|отсортировалитеореме о минимуме/максимуме скалярного произведения]] за <tex>O(n \log n)</tex>, так как мы сопоставляем две последовательности, подходящие под условия теоремы. Алгоритм работает за <tex>O(n + n \log n)</tex>

===Вариант 3===Так как [[Сортировка|сортировка]] весов занимает <tex> 1 O(n \mid r_ilog n)</tex> время,p_i = 1 \mid то асимптотика времени работы алгорита равна <tex>O(n + n \sum f_ilog n)</tex>.

Эта реализация использует [[Двоичная_куча|двоичную кучу]] * <tex>\mathtt{HeapQ}</tex> {{---}} обычная [[Очередь | очередь]], в которой операции вставки и извлечения выполняются за работы изначально располагаются в отсортированном по <tex>O(\log n)r_i</tex>порядке, а операция поиска максимального элемента за <tex>O(1)</tex> <tex> S \leftarrow \{1 \ldots n\}</tex> * <tex> \mathtt{timeP} \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> \mathtt{time} \leftarrow 1</tex> <tex> \mathtt{answer} \leftarrow 0</tex>====Алгоритм 1==== '''while''' <tex>\mathtt{Q} \neq \varnothing </tex> '''and''' <tex>\mathtt{P} \neq \varnothing </tex>Множество '''if''' <tex>S\mathtt{Q} \neq \varnothing </tex> станет пустым не позже, чем через <tex>n + j \maxleftarrow \limits_mathtt{i = 1 Q.head()}</tex> '''if''' <tex>\mathtt{time} < r_j</tex> <tex>\ldots nmathtt{time} r_\leftarrow r_j</tex> '''while''' <tex> \mathtt{itime}\geqslant r_j</tex> шагов цикла <tex>\mathtt{P. Определить максимум в множестве можно за время insert}(w_j)</tex> <tex>O\mathtt{Q.pop()}</tex> '''if''' <tex>\mathtt{Q} = \log nvarnothing </tex> '''break''' '''else''' <tex> j \leftarrow \mathtt{Q.head()}</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n \mathtt{Answer} \leftarrow \mathtt{Answer} + \maxmathtt{time} \limits_cdot \mathtt{i = 1 P.extractMax()} </tex> <tex> \ldots nmathtt{time} r_\texttt{i++})\log n)</tex>

====Алгоритм 2====Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.В начале алгоритма мы добавляем все элементы работы сортируются по <tex>w_ir_i</tex> в двоичную кучу тратя на это , из очереди <tex>O(n \log n)mathtt{Q}</tex> времени. Затем мы тратим достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>O(n \log n)mathtt{P}</tex> на получение ответа. Тогда суммарное время , поэтому итоговая асимптотика времени работы алгоритма составит составляет <tex>O(n \log n + n \log n)</tex> что есть <tex>O(n \log n)</tex> времени.