Задача
Ужляндія, як відомо, країна з розвиненими торговими відносинами.
Степан вирішив спробувати зайнятися торгівлею і підзаробити собі на відпустку продажем комп’ютерної техніки. Для цього йому необхідно закуповувати техніку у інших продавців. Перш ніж почати роботу, він вирішив постежити за подіями на ринку Ужляндії і придумати, як отримувати найбільший прибуток.
Степан дізнався, що кожен продавець продає один комп’ютер, і кожен покупець готовий купити рівно один комп’ютер. Всього на ринку торгують [latex]N[/latex] продавців, вартість комп’ютера у [latex]i[/latex]-го з них дорівнює [latex]A_{i}[/latex] Ужляндських монет, причому ціни можуть відрізнятися у різних продавців. Крім того, він знайшов для себе [latex]M[/latex] потенційних покупців, кожен з яких хоче купити комп’ютер за [latex]B_{i}[/latex] монет. При цьому сам Степан може купити і продати будь-яку кількість комп’ютерів.
Степану необхідно отримати найбільший прибуток (вигідно купити і вигідно продати). Тому він звернувся за допомогою до Вас — кращому програмісту Ужляндії.
Формат вхідних даних
Перший рядок вхідного файлу містить розділення одиночним пропуском два цілих числа [latex]N, M (1 \leqslant N, M \leqslant 10^{5})[/latex] — кількість продавців на ринку Байтландіі і кількість потенційних покупців відповідно.
Другий рядок містить [latex]N[/latex] цілих чисел [latex]A_{i} (0 \leqslant A_{i} \leqslant 10^{9})[/latex] — вартості, за якими продавці готові продавати комп’ютери.
Третій рядок містить [latex]M[/latex] цілих чисел [latex]B_{i} (0 \leqslant B_{i} \leqslant 10^{9})[/latex] — суми, які потенційні покупці готові віддати при покупці комп’ютера.
Формат вихідних даних
Перший рядок вихідного файлу має містити одне ціле число [latex]S[/latex] — розмір максимальної вигоди в монетах, яку може отримати Степан.
Тести
| № | Вхідні дані | Вихідні дані | Пояснення до прикладів | |
| 1 | 2 3 1 1 3 3 3 |
4 | Степан купує комп’ютери у 1-го і 2-го продавців і продає їх будь-яким двом покупцям. |
|
| 2 | 6 5 5 10 8 4 7 2 3 1 11 18 9 |
27 | Степану найбільш вигідно купити комп’ютери у 1-го, 4-го і 6-го продавців і продати 3-му, 4-му і 5-му покупцям. | |
| 3 | 4 5 6 7 9 8 3 3 5 1 2 |
0 | Степану невигідно закуповувати техніку, адже ціни продавців перевищують суми, які готові віддати покупці. | |
| 4 | 4 5 4 4 4 4 6 4 3 9 2 |
7 | Степану байдуже в кого купувати комп’ютери, але продати вигідно їх він зможе лише 1-му і 4-му покупцям. | |
| 5 | 3 3 5 1 3 9 8 6 |
14 | Степан купує всі комп’ютери, адже всіх їх він зможе вигідно продати. | |
| 6 | 4 1 2 5 4 6 8 |
6 | Покупець лише один, тому Степан має купити комп’ютер тільки у 1-го продавця. | |
| 7 | 3 6 1 7 4 0 0 0 0 0 0 |
0 | Клієнти є, але ніхто з них не збирається платити, тож Степан не отримає прибутку. | |
| 8 | 4 2 0 7 4 6 0 3 |
3 | Перший продавець віддає свій комп’ютер безкоштовно, а другий покупець готовий заплатити. Отже, Степан може заробити. | |
| 9 | 1 5 5 5 7 9 3 4 |
4 | Хоча покупців багато, але продавець лише один. Степан має продати комп’ютер 3-му клієнту. |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <algorithm> using namespace std; bool decrease(int a, int b) { return a > b; } int main() { int N, M, i = 0; cin >> N >> M; int * dealers = new int[N]; //створюємо масив вартостей, за якими продавці готові продавати комп'ютери for (int i = 0; i < N; i++) { cin >> dealers[i]; } int * clients = new int[M]; //створюємо масив сум, які покупці готові віддати при покупці комп'ютера for (int i = 0; i < M; i++) { cin >> clients[i]; } sort(dealers, dealers + N); //відсортуємо масив за зростанням ціни sort(clients, clients + M, decrease); //відсортуємо масив за спаданням ціни long int S = 0; while (dealers[i] < clients[i] && i < N) { S += (clients[i] - dealers[i]); //розраховуємо вигоду i++; } cout << S; return 0; } |
Розв’язок
Щоб отримати маскимальну вигоду, Степан має купувати комп’ютери за найменшою ціною, а продавати якомога дорожче. Отже, потрібно створити масиви і відсортувати їх: масив вартостей, за якими продавці готові продавати комп’ютери — за зростанням; масив сум, які потенційні покупці готові віддати при покупці комп’ютера — за спаданням. Далі створюємо цикл, за допомогою якого розраховуємо вигоду від реалізації кожного комп’ютера. Оскільки масиви відсортовані, то, як тільки прибуток стане від’ємним або нульовим, можемо припинити розрахунки і вивести розмір максимальної вигоди.
Посилання
Код на ideone
Задача на e-olymp
Зарахований розв’язок на e-olymp