Изменения

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

Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_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>

Эта реализация использует Перед началом алгоритма [[Двоичная_кучаСортировка|двоичную кучуотсортируем]] <tex>\mathtt{Heap}</tex> в которой операции вставки и извлечения выполняются за <tex>O(\log n)</tex>, а операция поиска максимального элемента за <tex>O(1)</tex> <tex> S \leftarrow \{1 \ldots n\}</tex>работы по порядку неубывания веса. <tex> \mathtt{time} \leftarrow 0r_1</tex>

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_{ji}</tex> '''else''' <tex> \mathtt{time++}\leftarrow r_i</tex> ===Сложность алгоритмов=======Алгоритм 1====Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \maxmathtt{Answer} \limits_{i = 1 leftarrow \ldots n} r_mathtt{iAnswer}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_mathtt{i = 1 time} \ldots n} r_cdot w_{i})\log n)</tex>

====Алгоритм 2====В начале алгоритма мы добавляем все элементы <tex>w_i</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+ 1))</tex> времени.