Mice and holes#10173

Mice and holes (Editorial)

Sort the coordinates of mice and holes accordingly in arrays $a$ and $b$ . Mouse $a_{i}$ a_i should hide in hole $b_{i}$ b_i. Compute the maximum among the differences of absolute values $∣ b_{i} - a_{i} ∣$ | b_i - a_i |.

Example

Sort arrays with coordinates of mice and holes. Assign mice $a_{i}$ a_i to the hole $b_{i}$ b_i.

The answer $2$ is achieved for the fourth mouse, which should run from the point with coordinate $9$ to the hole with coordinate $11$ .

Algorithm implementation

Declare the arrays $a$ and $b$ .

#define MAX 100001
int a[MAX], b[MAX];

Read the input data.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);
for (i = 0; i < n; i++)
  scanf("%d", &b[i]);

Sort the arrays.

sort(a, a + n);
sort(b, b + n);

Compute the maximum differences among the absolute values of $∣ 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]);

Print the answer.

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

Java implementation

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 implementation

Read the input data.

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

Sort the arrays.

a.sort()
b.sort()

Compute the maximum differences among the absolute values of $∣ 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 the answer.

print(res)