Степан - бізнесмен#83

Степан - бізнесмен (Розбір)

Степан купує комп'ютери у продавців і перепродує покупцям, причому кількість угод не обмежена. Прибуток від однієї угоди «купив у продавця з ціною , продав покупцю за » дорівнює B - A, і брати таку угоду має сенс лише коли B > A.

Отже, треба скласти пари «продавець — покупець», що максимізують суму додатних різниць.

Тут працює природна жадібність: найдорожчим покупцям слід продавати найдешевші комп'ютери. Відсортуємо ціни продавців за зростанням, а суми покупців за спаданням, і зіставимо їх по порядку: A_1 з B_1, A_2 з B_2 і так далі.

Тепер ідемо по парах і додаємо до прибутку B_i - A_i, доки ця різниця додатна. Щойно B_i \le A_i, можна зупинятися: далі лише спадає, а лише зростає, тому всі наступні різниці теж будуть недодатними.

Чому таке зіставлення оптимальне? Якщо в оптимальному наборі угод дешевший комп'ютер продано дешевшому покупцю, а дорожчий — дорожчому, то обмін покупців місцями не зменшить сумарний прибуток. Повторюючи такі обміни, приходимо саме до описаного сортування.

Складність — \mathcal{O}(N \log N + M \log M). Прибуток може бути великим, тому накопичуйте його у 64-бітному типі.