Задача

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

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

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

Код

#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;
}

#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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Валентина Михайліщук

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