Условие такое. Даны два набора чисел, по n в каждом. К примеру:
1) 2 5 1
2) 3 3 1
Мы можем расположить числа в произвольном порядке, например:
1) 1 2 5
2) 3 3 1
или
1) 5 2 1
2) 3 1 3
Выбрав некоторое расположение, мы умножаем числа попарно, и складываем результаты. Например:
1) 5 1 2
2) 1 3 3
5*1 + 1*3 + 2*3 = 14
Нужно расположить числа так, чтобы полученное произведение оказалось максимально возможным.
Решение: нужно просто отсортировать оба массива. В нашем случае:
1) 1 2 5
2) 1 3 3
1*1 + 2*3 + 5*3 = 22
Чтобы доказать, что это правильно, покажем, что, сортируя, мы улучшаем результат. Пусть на некотором месте в верхней строке стоит число А, в нижней строке - а, а на другом месте, в верхней строке стоит В, в нижней - в. Имеем: Aa+Bb. Легко убедиться, что множить наоборот, т.е. Ab+Ba, будет выгоднее только тогда, когда порядок чисел A,B и a,b - разный, т.е. когда (A-B)(a-b)<0 - это получается непосредственно из предположения, что Ab+Ba>Aa+Bb. Применяя это рассуждение много раз, получим что-то вроде пузырьковой сортировки
