Тема: Timus 1783. Nuclear Arms Race
Здравствуйте!
Подскажите пожалуйста как решить эту задачу.
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Timus 1783. Nuclear Arms Race
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Здравствуйте!
Подскажите пожалуйста как решить эту задачу.
Вроде есть кое какая идея, но реализовав ее я получаю WA 5, может быть алгоритм верный, но я допустил баг. В общем вот какая идея, построим выпуклую оболочку. Теперь для всех точек по абсциссе ответ будет ближайшая сверху целая точка по данному графику. Причем при нахождении очередной точки обновляем левый конец отрезка (хотя не очень уверен что это необходимо). Извиняюсь если объяснил смутно. Может ли кто-нибудь опровергнуть этот алгоритм или подтвердить его. Как мне кажется я упустил какой-то маленький крайний случай?
UPD НЕВЕРНАЯ ИДЕЯ, не правильно понял условие
UPD2 каждый раз считаете максимум среди следующих m высот, если текущая cur, то это значение равно
max{(a[i] - cur) / 1, (a[i + 1] - cur) / 2, ... (a[i + m - 1] - cur) / m}
везде округляете вверх, выводите ответ и обновляете текущую высоту. AC за 0.046с
Спасибо!:)
попробую закодить.
Как вы до этого додумались?
Решал задачи...
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Timus 1783. Nuclear Arms Race