Миші та нори#10173

Миші та нори (Розбір)

Відсортуємо координати мишей і нір відповідно в масивах $a$ і $b$ . Миша $a_{i}$ a_i повинна сховатися в нору $b_{i}$ b_i. Обчислюємо максимум серед модулів різниць $∣ b_{i} - a_{i} ∣$ | b_i - a_i |.

Приклад

Відсортуємо масиви з координатами мишей і нір. Миші $a_{i}$ a_i поставимо у відповідність нору $b_{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} ∣$ | 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();
  }
}

Java

Python реалізація

Читаємо вхідні дані.

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

Сортуємо масиви.

a.sort()
b.sort()

Обчислюємо максимум серед модулів різниць $∣ b_{i} - a_{i} ∣$ | 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)