317
правок
Изменения
→Второй шаг
==== Первый шаг ====
На первом шаге мы релаксируем дедлайны всех работ, кроме листовой, в соответствии с предыдущим пунктом.
* Класс <tex>\mathtt {Job}</tex> имеет поля В массиве <tex>\mathtt d</tex> {{---}} дедлайн, хранятся дедлайны работ.* В массиве <tex>\mathtt {parents}</tex> {{---}} массив предков, <tex>\mathtt childi</tex> {{---}} ребенокй работы.* В переменной <tex>\mathtt i</tex> хранится лист. номер листа (Он он один, см. условие задачи). '''Deque<Jobint>''' deque = <tex>\varnothing</tex>
deque.push(i)
'''while''' '''not''' deque.isEmpty
'''Jobint''' j = deque.removeFirst() '''for''' k '''in''' i.parents[j] d[k.d ] = min(d[k.], d, [j.d ] - 1)
deque.addLast(k)
* Массив <tex>\mathtt q</tex> хранит информацию о количестве работ, готовых к исполнению (находящихся в очереди) в момент времени <tex>t</tex>.
* Массив <tex>\mathtt x</tex> хранит информацию о начале выполнения работы <tex>i</tex>.
* В массиве <tex>\mathtt {child}</tex> хранится индекс ребенка <tex>i</tex>-й работы.
F = 0
'''if''' q[t] == m
F = t + 1
'''int''' j = child[i.child()]
r[j] = max(r[j], t + 1)
В результате ответ можно получить, зная конечный массив <tex>\mathtt x</tex> и делайны работ: <tex>L_{max} = \max\limits_i \{(\mathtt x[i] + 1 - \mathtt j[d_{i].d\}</tex>), так как все работы выполняются единицу времени, следовательно, где <tex> C_{i} = \mathtt jx[i] + 1</tex> {{---}} массив работ, описанный в первом пункте. Можно заметить, что при вычислении ответа неважно, какие дедлайны использовать, начальные или релаксированные, потому что для любого <tex>k</tex> и его предка <tex>i</tex> либо производится релаксация и выполняется неравенство равенство <tex> \mathtt j[d_{k].d \leqslant \mathtt j[} = d_{i].d } - 1</tex>, а значит, после релаксации минимум максимум не изменится, поскольку при замене дедлайна на меньший максимум увеличится, а новое значение <tex>L_{k}</tex> будет равно <tex>L_{i}</tex>, либо мы не делали релаксацию, и значение <tex>d_{k}</tex>, и, следовательно, <tex>L_{k}</tex> не поменяются. (При условии, что существует правильное расписание)
=== Доказательство корректности ===
