Распределение
Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов [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 |
import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner scan = new Scanner(System.in); int size = scan.nextInt(); long arr1[] = new long [size]; long arr2[] = new long [size]; for(int i = 0; i < size; i++){ arr1[i] = scan.nextInt(); } for(int i = 0; i < size; i++){ arr2[i] = scan.nextInt(); } long tmp = 0; for(int i = 0; i < size; i++){ tmp+= Math.abs(arr2[i] - arr1[i]); } System.out.println (tmp / 2); } } |
Решение задачи
Данная задача решается вычислением и суммированием разности соответствующих элементов второго массива и первого. Таким образом мы найдем количество воинов, которых не хватает и которых надо перевести в другой отряд. Возьмём эту разность по модулю, затем поделим на [latex]2[/latex], так как мы учитывали всех воинов. В итоге получим минимальное количество переводов из одного отряда в другой.
Ссылки
• Задача на e-olymp.
• Решение на сайте ideone.