Изменения

Алгоритм изменения сроков:На первом шаге мы релаксируем дедлайны всех работ, кроме листовой, в соответствии с предыдущим пунктом.* В массиве <tex>\mathtt jd</tex> хранятся работы, имеющие поле дедлайны работ.* В массиве <tex>\mathtt d{parents}</tex> {{---}} дедлайнмассив предков <tex>i</tex>-й работы. '''int''' i = 0 deque = * В переменной <tex>\varnothingmathtt i</tex>хранится номер листа (он один, см. условие задачи). '''for''' '''Deque<int''' k = 1 .. n <font color=green> // ищем лист в дереве, из него будет производиться обход дерева </font> '''if''' j[k].parents =deque = <tex>\varnothing</tex> i = k <font color=green> // такая вершина только одна (intree-дерево из условия) </font>

i '''int''' j = deque.removeFirst() '''for''' '''int''' k '''in''' parents[j[i].parents jd[k].d = min(jd[k]., d, [j[i].d - 1)

'''int''' j = child[i.child()]

В результате ответ можно получить, зная конечный массив <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> не поменяются. (При условии, что существует правильное расписание)