Задача
Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношения. Коэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?
Входные данные
Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.
Выходные данные
Выведите одно число — ответ на задачу.
Тесты
№ |
Входные данные |
Выходные данные |
| 1 |
2
-3 -5
3 5
|
0 |
| 2 | 1 5 -2 |
0 |
| 3 | 5 -5 -2 -1 0 4 5 4 0 0 -1 |
4 |
| 4 | 9 1000 -22 333 -56 1 2 -77 -650 10 -7 166 -333 90 -565 12 788 -800 111 |
523 |
Код программы
|
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 |
import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int n; n = in.nextInt(); int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i < n; i ++) a[i] = in.nextInt(); // Считываем массивы for (int i = 0; i < n; i ++) b[i] = in.nextInt(); Arrays.sort(a);// Сортируем массивы Arrays.sort(b);// Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке for (int i = 0; i < n; i ++) a[i] += b[n - i - 1]; // Суммируем элементы int maxa = a[0], mina = a[0]; for (int i = 0; i < n; i ++) { maxa = Math.max(maxa, a[i]); // Находим минимальный и максимальный элементы mina = Math.min(mina, a[i]); } out.println(maxa - mina);// Разность минимального и максимального и будет самым маленьким индексом любви out.flush(); } } |
Решение
Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.
Ссылки
Условие задачи e-olymp
Код решения ideone