1679
правок
Изменения
→Бинарный поиск по ответу
== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.
Этим методом решаются:
* <tex> O \mid p_{ij} = 1 \mid \sum U_I </tex>
* <tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex>
* <tex> Q \mid pmtn, r_i \mid L_{max} </tex>
=== Примеры ===
==== O | p_ij = 1| Sum(U_i) ====
