e-olymp 7240. Степан — бізнесмен

Задача

Ужляндія, як відомо, країна з розвиненими торговими відносинами.

Степан вирішив спробувати зайнятися торгівлею і підзаробити собі на відпустку продажем комп’ютерної техніки. Для цього йому необхідно закуповувати техніку у інших продавців. Перш ніж почати роботу, він вирішив постежити за подіями на ринку Ужляндії і придумати, як отримувати найбільший прибуток.

Степан дізнався, що кожен продавець продає один комп’ютер, і кожен покупець готовий купити рівно один комп’ютер. Всього на ринку торгують [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-му клієнту.

Код

Розв’язок

Щоб отримати маскимальну вигоду, Степан має купувати комп’ютери за найменшою ціною, а продавати якомога дорожче. Отже, потрібно створити масиви і відсортувати їх: масив вартостей, за якими продавці готові продавати комп’ютери — за зростанням; масив сум, які потенційні покупці готові віддати при покупці комп’ютера — за спаданням. Далі створюємо цикл, за допомогою якого розраховуємо вигоду від реалізації кожного комп’ютера. Оскільки масиви відсортовані, то, як тільки прибуток стане від’ємним або нульовим, можемо припинити розрахунки і вивести розмір максимальної вигоди.

Посилання

Код на ideone
Задача на e-olymp
Зарахований розв’язок на e-olymp

4 thoughts on “e-olymp 7240. Степан — бізнесмен

  1. — Тесты должны проверять все наиболее характерные случаи. Может быть ситуация, когда продавать нечего? Где тест? А может быть ситуация, когда продать можно все компьютеры? Где тест? А если вообще нет покупателей? Или продавцов? Это называется «покрытие тестами». После написания программы желательно попытаться провалить ее новыми тестами.
    — Объявлять переменные лучше непосредственно перед их использованием. Вы так и делали. Кроме одного места. Уверен, что это было случайно. Вот только не уверен, что именно было случайно 🙂
    — Вы знаете об операции «увеличить на»? Почему лучше использовать её?
    — Посмотрите, пожалуйста, в каких случаях принято использовать двоеточие.
    — «прибуток прибуток»
    — Знаки меньше либо равно должны выглядеть так, как в ваших учебниках.

    • Ошибки исправила. Тесты дополнила. Ситуации, когда нет продавцов или покупателей, быть не может, так как по условию задачи M, N больше либо равно 1. Ситуация, когда можно продать все компьютеры, описана в первом тесте.
      Двоеточие я использовала, так как вторая часть сложного предложения поясняет и дополняет первую.

    • — Заголовок является отдельным предложением. В конце заголовков не принято ставить точки или двоеточия. Пожалуйста, уберите двоеточия в конце заголовков.
      — Пожалуйста, уберите кириллицу из адреса (постоянной ссылки). Это создает проблемы. «e-olymp-7240» или даже «7240» вполне подходящий адрес этой для работы на сайте.
      — С количеством продавцов и покупателей вы правы. Нулевые стоимости проверять будем?

    • Добавила еще несколько тестов. Ссылку исправила.

Добавить комментарий