<tex> 1 \mid p_i = 1\mid \sum C_i</tex>
Этот случай простейший. Ответом будет <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>.
===Вариант 2===
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</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>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>
'''Псевдокод'''
<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>
==Основная задача==
===Описание алгоритма===
===Псевдокод===
====Алгоритм Реализация 1====
<tex> S \leftarrow \{1 \ldots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
<tex> \mathtt{time++}</tex>
====Алгоритм 2====Этот алгоритм реализован с помощью [[Двоичная_куча|двоичной кучи]] Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \mathttldots n} r_{Heapi}</tex> шагов цикла. Определить максимум в которой операции вставки и извлечения выполняются множестве можно за время <tex>O(\log n)</tex>, а операция поиска максимального элемента за используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O(1)</tex> <tex> S (n + \leftarrow max\limits_{i = 1 \ldots n\}</tex> <tex> \mathttr_{timei} )\leftarrow 0log n)</tex> ====Реализация 2====* <tex> \mathtt{answerQ} \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 r_i</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_{jP}</tex> <tex> \mathtt{time++{---}}</tex>[[Приоритетные очереди | приоритетная очередь]] по максимуму.
В начале алгоритма мы добавляем все элементы <tex>w_i\mathtt{time} \leftarrow 1</tex> <tex> \mathtt{answer} \leftarrow 0</tex> '''while''' <tex>\mathtt{Q} \neq \varnothing </tex> в двоичную кучу тратя на это '''and''' <tex>O\mathtt{P} \neq \varnothing </tex> '''if''' <tex>\mathtt{Q} \neq \varnothing </tex> <tex> j \leftarrow \mathtt{Q.head(n )}</tex> '''if''' <tex>\mathtt{time} < r_j</tex> <tex>\mathtt{time} \leftarrow r_j</tex> '''while''' <tex> \mathtt{time} \geqslant r_j</tex> <tex>\log nmathtt{P.insert}(w_j)</tex> времени <tex>\mathtt{Q. Затем мы тратим pop()}</tex>O '''if''' <tex>\mathtt{Q} = \varnothing </tex> '''break''' '''else''' <tex> j \leftarrow \mathtt{Q.head(n \log n)}</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n mathtt{Answer} \leftarrow \mathtt{Answer} + n \log nmathtt{time} \cdot \mathtt{P.extractMax()} </tex> что есть <tex>O(n \log n)mathtt{time}\texttt{++}</tex> времени.
===Сложность алгоритма===Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.Множество В начале работы сортируются по <tex>Sr_i</tex> станет пустым не позже, чем через из очереди <tex>n + \max\limits_{i = 1 \ldots n} r_mathtt{iQ}</tex> шагов цикла. Определить максимум в множестве можно за время достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>O(\log n)mathtt{P}</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex>.
==См. также==
