251
правка
Изменения
Нет описания правки
==Псевдокод==
'''function ''' scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>'''
<tex>I = \varnothing </tex>
<tex>J = \varnothing </tex>
'''pair<int[n], int[n]>''' ans
<tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i, \ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
'''if''' <tex>a_{x} < \geqslant b_{y}</tex> Поменять местами первый и второй станок Пересчитать <tex>I, J, x</tex> Запомнить, что поменяли Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</tex> Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>I \setminus \{x\}</tex><br/> От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex> От правой границы {{---}} <tex>C_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/> ans = пара из расписания для первого станка и расписания для воторого станка '''return''' ans '''ifelse''' станки меняли ans = scheduling(b, a) Меняем местамирасписания для станков в ans поменять их обратно '''return''' ans
==Сложность алгоритма==
