Про то, что это "галочка"с минимумом в нуле - ясно. Я, видимо, какую-то очевидность в ваших рассуждениях не могу уловить.

Не совсем. График модуля - это линейная функция, потом излом и потом опять линейная функция. Линейную функцию можно описать двумя параметрами - ну, например, значением в нуле и наклоном. Сумма линейных функций - это тоже линейная функция, значение в нуле и наклон которой есть сумма параметров слагаемых. Соответственно, сумма некоторого количества сдвинутых модулей есть кусочно-линейная функция, каждому излому которой соответствует излом хотя бы одного модуля. Чтобы перейти от параметров прямых слева от вершины к параметрам справа, нужно из них вычесть параметры левых половинок графиков модулей, вершины которых образуют этот излом, и прибавить параметры их правых половинок. Ну а если вспомнить, что минимум кусочно-линейной функции достигается на концах или в точках излома - дальше всё тривиально. Ну и не забыть, что излом модуля может для конкретного отсчета оказаться вне допустимого диапазона параметра.

Есть ещё одна деталь, которую я в прошлый раз не домыслил. Слева от излома модуля его производная равна -1, справа +1. Так что чтобы найти глобальный минимум суммы модулей - нужно просто рассортировать модули по возрастанию координат вершин, и взять координату вершины, оказавшейся в середине списка. Если она лежит вне допустимого отрезка - взять ближайший к ней конец отрезка.

Врочем, вру. У вас модули умножены на некоторый коэффициент, поэтому их наклон не единица.

Для двухмерного случая надо минимизировать: Sum(|x * a[i] + y * b[i]|).
Рассматриваем только один из четырех случаев: x + y = 1.
Для каждого члена суммы излом будет только в одной точке: x = b[i] / (b[i] - a[i]).
Про вычитание/сложение половинок слева/справа от излома не понял.
P.S. Если минимум находится в одном из изломов, то достаточно же пробежаться по всем изломам и найти минимум: посчитать сумму для каждой точки излома и выбрать минимальную.

Сообщение отредактировал getch - Nov 22 2010, 21:57

Слева от вершины вклад от некоторого модуля в сумму будет, например, , а справа -

Ух, так и не понял про половинки. Зачем они? И почему некорректно пробежаться по точками излома и точкам слева-справа?

Сообщение отредактировал getch - Nov 22 2010, 22:06

Можно и в лоб. Но на длинах в несколько десятков тысяч точек будет уже долго.

Извините, я не понял Ваш вариант решения. Он разве не в лоб?
Я не дошел до понимания вашего решения.

Он NlogN, а в лоб - это квадрат. Вы как собираетесь находить величину функции в каждом изломе?

Тупо считать сумму.
Ваше решение для Вас очевидно. Но я не понял его. Можно пошагово с момента, когда точки излома известны?

Пошагово - сортируете, потом выкидываете все точки вне отрезка [0,1], сворачивая их вклад в суммы линейных функций, потом оставшиеся точки сортируете по координате вершины, потом проходите слева направо по всем точкам плюс края отрезка, сравниваете их высоту, но только высоту считаете не суммируя по всему массиву вклад всех точек для данной координаты, а переходя от предыдущей точки к следующей, изменяя вклад перескакиваемой точки и обновляя вклад всех остальных скопом.

Для векторов {a1, a2, a2} и {b1, b2, b3} можете показать? Возможно, у меня незнание терминологии. Потому как "сворачивать" - не понимаю. Изменять вклад перескакиваемой точки - это как?

Сообщение отредактировал getch - Nov 23 2010, 10:40

Мне вам код написать? С сортировкой?
Представьте что вы оказались слева от двух вершин модулей. Как выглядит график суммы модулей в вашей окрестности? Это линейная функция, иначе говоря, прямая. Как можно описать эту прямую? Уравнением y=a*x+b, причем, параметры a и b равны суммам параметров от слагаемых модулей в окрестности рассматриваемой точки.
Пусть вы прибавили график ещё одного модуля, но вы всё ещё слева от всех их изломов. Что изменится? Уравнение останется то же, но к её значению в нуле и наклону прибавятся значение в нуле и наклон от третьего слагаемого. И так далее.
Теперь предположим, что вы по этой прямой, двигаясь вправо, дошли до самой левой вершины и хотите её обойти. Что будет в промежутке между первой и второй вершиной? Тоже прямая. Какие будут её параметры? Её параметры будут почти такие же, как и слева от рассматриваемой вершины, изменится в сумме только вклад от модуля, которому принадлежит эта вершина. Это изменение можно учесть и идти дальше.

Как только пойму ваше решение, код напишу сразу сам напишу. Проблема лишь в понимании Вашего решения.

1. Находясь слева мы просто суммируем линейный функции, убрав знаки модулей.
2. Проходя первый излом, мы уже не суммируем, а вычитаем линейную функцию того слагаемого, которому принаджедит излом.

В итоге, если слагаемых N, то имеем N+2 линейные функции. Что нам это дает?

Сообщение отредактировал getch - Nov 23 2010, 11:07

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



У слагаемого две различные линейные функции, одна - слева, другая - справа. Переходя слева направо вычитаете левую и прибавляете правую.

Да, это понял, так получим N+2 линейные функции.

Прошу, поясните эту цитату.
Вот так выглядит функция, минимум которой ищется: