<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>w_i C_i O(n \geqslant w_j C_jlog n)</tex>время, где то асимптотика времени работы алгорита равна <tex>w_i C_i</tex> произведение на текущем шаге до сортировки, а <tex>w_j C_j</tex> после. Полученное произведение <tex>w_j C_j</tex> «более похоже» на оптимальное, чем произведение <tex>w_i C_iO(n + n \log n)</tex>. Тогда применение жадного алгоритма дает верный ответ.
Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex>
===Вариант 3===
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</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>
==Основная задача==
===Описание алгоритма===
====Реализация 2====
Перед началом алгоритма * <tex>\mathtt{Q}</tex> {{---}} обычная [[СортировкаОчередь |отсортируемочередь]] , в которой работы изначально располагаются в отсортированном по порядку неубывания веса<tex>r_i</tex> порядке,* <tex>\mathtt{P}</tex> {{---}} [[Приоритетные очереди | приоритетная очередь]] по максимуму. <tex> \mathtt{time} \leftarrow r_11</tex> <tex> \mathtt{answer} \leftarrow 0</tex> '''forwhile''' <tex>i \leftarrow 1 mathtt{Q} \neq \varnothing </tex> '''toand''' <tex>n\mathtt{P} \neq \varnothing </tex> '''doif'''<tex>\mathtt{Q} \neq \varnothing </tex> <tex> j \leftarrow \mathtt{Q.head()}</tex> '''if''' <tex> r_\mathtt{itime} \leqslant < r_j</tex> <tex>\mathtt{time}\leftarrow r_j</tex> '''while''' <tex> \mathtt{Answertime} \leftarrow geqslant r_j</tex> <tex>\mathtt{AnswerP.insert} + (w_j)</tex> <tex>\mathtt{timeQ.pop()} </tex> '''if''' <tex>\cdot w_mathtt{iQ}= \varnothing </tex> '''break''' '''else''' <tex> j \leftarrow \mathtt{timeQ.head()} \leftarrow r_i</tex> <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_\mathtt{P.extractMax()} </tex> <tex> \mathtt{time}\texttt{i++}</tex>
Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.В начале алгоритма сортируем работы сортируются по <tex>O(n \log n)r_i</tex> времени. Затем мы тратим , из очереди <tex>O(n)\mathtt{Q}</tex> на получение ответа. Тогда суммарное время работы алгоритма составит достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>O(n \log n + n )mathtt{P}</tex> что есть , поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n (\log n + 1))</tex> времени.
==См. также==
