Распределение
Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов [latex]N[/latex] различных отрядов, которые были отправлены на завоевания. Однако прибывшие лишь только сейчас разведчики донесли о силах противников, скопленных в этих поселениях, что естественно скорректировало планы Оргрима. И теперь он хочет произвести перераспределение войск по отрядам, переводя воинов из одного отряда в другой. При этом, чтобы не создавать неразбериху в рядах своей армии и выполнить перераспределение как можно быстрее, количество таких переводов должно быть минимально возможным (за один раз переводится один солдат из некоторого отряда в другой).
Напишите программу, которая определяет минимальное количество переводов для перераспределения войск.
Входные данные
Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.
Выходные данные
В выходной файл выведите минимально возможное количество переводов.
Тесты
| ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|
| 2 4 2 5 1 |
1 |
| 1 4 4 |
0 |
| 3 2 2 2 4 1 1 |
2 |
| 3 6 3 1 0 0 10 |
9 |
Код программы
|
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 |
#include <iostream> using namespace std; int main() { int size; cin >> size; long *arr1 = new long[size]; long *arr2 = new long[size]; for(int i = 0; i < size; i++){ cin >> arr1[i]; } for(int i = 0; i < size; i++){ cin >> arr2[i]; } long tmp = 0; for(int i = 0; i < size; i++){ tmp+= abs(arr2[i] - arr1[i]); } cout << tmp / 2; delete []arr1; delete []arr2; return 0; } |
Решение задачи
Данная задача решается вычислением и суммированием разности соответствующих элементов второго массива и первого. Таким образом мы найдем количество воинов, которых не хватает и которых надо перевести в другой отряд. Возьмём эту разность по модулю, затем поделим на [latex]2[/latex], так как мы учитывали всех воинов. В итоге получим минимальное количество переводов из одного отряда в другой.
Ссылки
• Задача на e-olymp.
• Решение на сайте ideone.
Сделайте правильные отступы в коде.
Описании решения задачи вместо слова «разницы» стоит писать разности. Также вы не указали, что суммируете разности.
В одном месте не оформили $N$ как формулу.
А! Вы раньше успели! А я после первой фразы пошел оливье пробовать 🙂