Матч 433, Королевское сокровище (RoyalTreasurer)

Дивизион 2, Уровень 1

Массивы a и b содержат одинаковое количество неотрицательных целых чисел. Рассмотрим сумму

S = a₀ * b₀ + a₁ * b₁ + … + a_n-1 * b_n-1

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

Класс: RoyalTreasurer

Метод: int minimalArrangement(vector<int> a, vector<int> b)

Ограничения: а и b содержат одинаковое количество элементов, от 1 до 50, 0 £ a[i], b[i] £ 100.

Вход. Массивы неотрицательных целых чисел a и b.

Выход. Наименьшее возможное значение суммы S.

Пример входа

a	b
{1,1,3}	{10,30,20}
{1,1,1,6,0}	{2,7,8,3,1}
{5,15,100,31,39,0,0,3,26}	{11,12,13,2,3,4,5,9,1}

Пример выхода

80

18

528

РЕШЕНИЕ

сортировка

Отсортируем элементы массива а по возрастанию, а b – по убыванию. Скалярное произведение векторов a и b является искомой наименьшей суммой. Очевидно, что это же значение можно получить переставляя только элементы массива а, сопоставив наименьший элемент массива а наибольшему элементу из b, второй наименьший элемент массива а второму наибольшему элементу из b, и так далее.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <set>

#include <numeric>

using namespace std;

class RoyalTreasurer

{

public:

int minimalArrangement(vector<int> a, vector<int> b)

{

sort(a.begin(),a.end()); sort(b.begin(),b.end(),greater<int>());

return inner_product(a.begin(),a.end(),b.begin(),0);

}

};