https://practice.geeksforgeeks.org/problems/assign-mice-holes/0

Given, N Mice and N holes are placed in a straight line. Each hole can accommodate only 1 mouse. A mouse can stay at his position, move one step right from x to x + 1, or move one step left from x to x -1. Any of these moves consumes 1 minute. Write a program to assign mice to holes so that the time when the last mouse gets inside a hole is minimized.

Input:
First line of input contains a single integer T, which denotes the number of test cases. T test cases follows, first line of each test case contains a single integer N which denotes the number of mice and holes. Second line of each test case contains N space separated integers which denotes the position of mice initially. Third line of each test case also contains N space separated integers which denotes the position of holes.

Output:
For each test case in a new line print the minimum time required in which all the mice can get into the holes.
Example:
Input:
2
3
4 -4 2
4 0 5
8
-10 -79 -79 67 93 -85 -28 -94
-2 9 69 25 -31 23 50 78
Output:
4
102

对洞和老鼠排序，每只老鼠选距离它最近的一个洞口。
可以证明这样选择不会造成更差的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int MAX=10000+10;
int m[MAX],h[MAX],t,n;
int main(){
	freopen("in","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%d",&m[i]);
		for(int i=0;i<n;i++)
			scanf("%d",&h[i]);
		sort(m,m+n);
		sort(h,h+n);
		int ans = 0; 
        for (int i=0; i<n; i++) 
            if (ans < abs(m[i]-h[i])) 
                ans = abs(m[i]-h[i]);
        printf("%d\n",ans);
	}
	return 0;
}