Ответы пользователя по тегу Алгоритмы
  • Имеет ли решение задача?

    @AndreyDaeron
    1. R = a1*|k-b1/a1| + a2*|k-b2/a2| + a3|k3-b3/a3| +… + an|k-bn/an| (если ai=0 — то за скобки не выносим и нам это пофиг.
    2. Очевидно, что такая функция кусочно-линейна относительна к на каждом из участков, к, для которых модули открываются с одинаковым знаком (предположим что а1/b1>b2/a2>...bn/an, если это не так — отсортируем что бы было так). Имеется ввиду что на участке [(ai/bi,(ai+1)/(bi+1)] функция будет линейна (!!! Это, в общем случае неверно для для (-inf,+inf).
    3. Поскольку она линейна, то её минимум будет достигнут в одной из точек ai/bi.
    4. ????? (перебираем все точки ai/bi)
    5. Profit

    И никакого бинарного поиска ))
    Ответ написан
    21 комментарий