10173. Мыши и норы

На прямой расположены n мышей и n норок. Каждая норка может вместить только 1 мышь. Мышь может оставаться на своем месте, перемещаться на один шаг вправо от x до x + 1 или на один шаг влево от x до x – 1. Любой из этих ходов занимает 1 минуту. Поставьте каждой мыши в соответствие норку так, чтобы минимизировать время, за которое последняя мышь спрячется в норке.

Вход. Первая строка содержит число n (n ≤ 10⁵). Вторая строка содержит координаты n мышей. Третья строка содержит координаты n норок. Координаты мышей и норок являются целыми числами от 0 до 10⁹.

Выход. Выведите наименьшее время, за которое последняя мышь спрячется в норке.

Пример входа	Пример выхода
4 3 6 1 9 5 3 11 2	2

РЕШЕНИЕ

жадность

Анализ алгоритма

Отсортируем координаты мышей и нор моответственно в массивах a и b. Мышь a[i] должна спрятаться в нору b[i]. Вычисляем максимум среди модулей разностей | b[i] – a[i] |.

Пример

Отсортируем массивы с координатами мышей и нор. Мыши a[i] поставим в соответствие нору b[i].

Ответ 2 достигается для четвертой мыши, которой следует бежать из точки с координатой 9 в нору с координатой 11.

Реализация алгоритма

Объявим рабочие массивы a и b.

#define MAX 100001

int a[MAX], b[MAX];

Читаем входные данные.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &a[i]);

for (i = 0; i < n; i++)

scanf("%d", &b[i]);

Сортируем массивы.

sort(a, a + n);

sort(b, b + n);

Вычисляем максимум среди модулей разностей | b[i] – a[i] |.

res = 0;

for (i = 0; i < n; i++)

if (abs(b[i] - a[i]) > res) res = abs(b[i] - a[i]);

Выводим ответ.

printf("%d\n", res);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Integer a[] = new Integer[n];

for(int i = 0; i < n; i++)

a[i] = con.nextInt();

Integer b[] = new Integer[n];

for(int i = 0; i < n; i++)

b[i] = con.nextInt();

Arrays.sort(a);

Arrays.sort(b);

int res = 0;

for (int i = 0; i < n; i++)

if (Math.abs(a[i] - b[i]) > res) res = Math.abs(a[i] - b[i]);

System.out.println(res);

con.close();

}

}

Python реализация

Читаем входные данные.

n = int(input())

a = list(map(int, input().split()))

b = list(map(int, input().split()))

Сортируем массивы.

a.sort()

b.sort()

Вычисляем максимум среди модулей разностей | b[i] – a[i] |.

res = 0

for i in range(n):

if abs(a[i] - b[i]) > res: res = abs(a[i] - b[i])

Выводим ответ.

print(res)