UniLecs #175. Госзакупки

Задача: администрация области занимается гос-закупками медицинского оборудования (томографы) для N городов. Для каждого города нужно определенное количество томографов. 

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

Вам необходимо оптимальным способом закупить нужное количество томографов каждому из городов в области.

Входные данные:

• priceArr[N] - в массиве представлены цены (цена указана за 1 томограф в млн.руб) томографов для N компаний.
• cityArr[N] - в массиве представлены количества томографов необходимые для каждого из N городов.

Вывод: минимальная сумма необходимая для закупки нужного количества томографов каждому из городов.

Пример:

priceArr = [20 млн.руб за 1 томограф, 10 млн.руб за 1 томограф]

cityArr = [необходимо 5 томографов, необходимо 6 томографов]

Answer = 160 млн.рублей

Идея: хоть задача и выглядит сложной, но она решается в пару действий. Так как по условию каждая компания должна быть связана только с одним любым городом, то нам достаточно найти минимальную сумму от суммы произведений Price(i) * City(j), где i,j от 1 до N.

Чтобы найти минимальную суммы от такого произведения достаточно:

1. Отсортировать массив с ценами по возрастанию.
2. Массив с количеством томографов для городов отсортировать по убыванию.
3. Найти сумму Price(i) * City(i), где i от 1 до N.

Т.е. городу с наибольшим количеством требуемых томографов мы закупим их по самой низкой цене среди поставщиков. А городу с наименьшим количеством требуемых томографов - по самой высокой цене среди поставщиков.

Вот такая вот гос-закупка :)

Реализация:

https://gist.github.com/unilecs/62b0b1c6820f290ad680f60756c11905

Play-test: https://dotnetfiddle.net/wiFzfr