1632
правки
Изменения
м
rollbackEdits.php mass rollback
=== Псевдокод ===
Алгоритм принимает на вход два массива {{---}} массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй {{---}} номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке. '''function''' scheduling(p: '''int'''[n], v: '''int'''[n]) -> '''(vector<int, int, int, int)>'''[m] '''int''' a time = 0<font color=green>// текущее время на всех станках</font> '''(vector<int, int, int, int)>'''[] ans <font color=green> // сюда вектор, куда будет записываться записан ответ</font>
sort(p) <font color=green>// сортируем времена обработки работ в невозрастающем порядке</font>
sort(v) <font color=green>// сортируем скорости обработки станков в невозрастающем порядке</font>
'''while''' p[1] > 0
Находим наибольший i такой, что p[i] > 0
'''int''' t dt = p[i] / v[1]<font color=green>// время обработки самой короткой доступной задачи на самом быстром станке</font>
'''for''' j = i '''downto''' k = max(1, i - m + 1)
ans[.push(1 + i - j].push(a, a j, time, time + t, jdt) <font color=green>// Назначаем работу j на станок <tex>M_{1+i-j}</tex> работу j на время от a time до a time + tdt</font> p[j] = p[j] - t dt * v[1 + i - j]<font color=green>// уменьшаем количество обработки, оставшейся для j-ой работы</font> a time = a time + tdt <font color=green>// обновляем текущее время</font> '''return ''' ans
=== Асимптотика ===
Сначала мы сортируем работы и станки, что занимает <tex> \mathcal{O}(n\log{n})</tex> и <tex> \mathcal{O}(m\log{m})</tex>. Так как мы можем предположитьпри <tex>m \geqslant n</tex>, что количество станков меньше или равно колиеству работ <tex>m \leqslant - n</tex>самых медленных станков можно не использовать, то в итоге сортировка займет <tex> \mathcal{O}(n\log{n})</tex>.
Количество прерываний ограничено числом <tex>(m-1) \cdot n - (1 + 2 + \ldots + (m - 1)) = (m - 1) \cdot (n - \cfrac{m}{2})</tex>.
В итоге всё вместе составляет асимптотику алгоритма <tex> \mathcal{O}(n\log{n} + mn)</tex>.
