Как применить троичный поиск для вызова SPOJ - KOPC12A

Question

Я пытался решить проблему KOPC12A в SPOJ.

Ссылка на проблему: http://www.spoj.com/problems/KOPC12A/

Проблема вкратце:

Для n зданий, каждая из которых имеет разную высоту (количество кирпичей), а каждое здание имеет стоимость добавления или удаления кирпича, найдите минимальную стоимость, чтобы все здания имели одинаковую высоту.

После попытки решить эту проблему, хотя и тщетно, я наткнулся на решение, в котором использовался троичный поиск, после сортировки входных данных по их высоте.

Я не смог понять, как затраты на выравнивание высот зданий становятся унимодальными (поскольку троичный поиск может применяться только к унимодальным функциям)

Это поставило меня в тупик, и я не смог продвинуться дальше.

Любое понимание этого очень ценится.

Спасибо-

Answer 1

Чтобы расширить комментарий sashas, мы можем определить (сильную) унимодальность функции f как условие

for all x < y < z, f(y) < max(f(x), f(z))

и (сильная) выпуклость функции f как условие

                          z - y        y - x
for all x < y < z, f(y) < ----- f(x) + ----- f(z).
                          z - x        z - x

Пусть высота зданий будет h1, ..., hn и стоимость изменения единицы будет c1, ..., cn, Цена f(h') сделать все здания высотой h' является

sum i in {1, ..., n} of ci |h' - hi|.

Теперь вот последовательность предложений, каждое из которых имеет довольно простое доказательство, приводящее посредством индукции к выводу, что f Унимодально

1. Функция g где g(x) = |x| выпуклый
2. Для всех констант hдля всех выпуклых функций g1, функция g2 где g2(x) = g1(x - h) выпуклый
3. Для всех констант c > 0для всех выпуклых функций g1, функция g2 где g2(x) = c g1(x) выпуклый
4. Для всех выпуклых функций g1 а также g2, функция g3 где g3(x) = g1(x) + g2(x) выпуклый
5. Все выпуклые функции унимодальны.