'''{{Задача о минимуме/максимуме скалярного произведения''' - |definition=задача о нахождении минимальной/максимальной суммы попарных произведений для двух заданных упорядоченных наборов чисел.}}
== Решение ==
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + ... + x_m y_m</tex>
|proof=
1. Будем считать, что <tex>x_i</tex> отсортирована по возрастанию. 2. Покажем, что если существуют пары чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <tex>x_i < x_j</tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i</tex> и <tex>y_j</tex>. Так таккак <tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j y_j > x_j y_i + x_i y_j</tex>. 3.Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>. 4. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность.
}}
== Литература ==
1. * Романовский И. В. Дискретный анализ. — 3-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 320— ISBN 5-7940-0114-3.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
