1

Тема: Timus 1783. Nuclear Arms Race

Здравствуйте!
Подскажите пожалуйста как решить эту задачу.

2 Отредактировано mansur115 (2011-07-16 11:44:13)

Re: Timus 1783. Nuclear Arms Race

Вроде есть кое какая идея, но реализовав ее я получаю 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с

3 Отредактировано mig47 (2011-07-16 21:44:03)

Re: Timus 1783. Nuclear Arms Race

Спасибо!:)
попробую закодить.

Как вы до этого додумались?

4

Re: Timus 1783. Nuclear Arms Race

Решал задачи...