A50147.小 Z 的手套
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
小 Z 从某市场批发了一些手套,具体地,共有 n 只左手手套和 m 只右手手套。
小 Z 准备手动将这些左手手套和右手手套组合起来拼成一对手套,并将其捐给有需要的人。其中 n 只左手手套编号为 1,2,⋯,n,第 i 只左手手套的尺码为 li;m 只右手手套编号为 1,2,⋯,m,第 i 只右手手套的尺码为 ri。
如果将第 i(1≤i≤n) 只左手手套和第 j(1≤j≤m) 只右手手套组合成一副手套,那么这副手套的丑陋程度为 ∣li−rj∣,即左手和右手手套尺码差值的绝对值。
小 Z 希望尽最大的可能帮助有需要的人,即他想要配对尽可能多的手套,并且使得配对成的手套的最大丑陋程度最小。请你求出这个最小值。
输入格式
第一行包含两个正整数 n 和 m ,分别表示左手手套和右手手套的数量。
第二行包含 n 个整数 l1,l2,⋯,ln 表示左手手套的尺码。
第二行包含 m 个整数 r1,r2,⋯,rm 表示右手手套的尺码。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入#1
2 3 2 3 1 2 3
输出#1
0
输入#2
4 3 2 39 41 45 39 42 46
输出#2
1
输入#3
5 5 7 6 1 2 10 9 11 6 3 12
输出#3
4
说明/提示
样例 1 解释
最多可以配对成功 2 副手套,分别让 (l1,r2),(l2,r3) 进行配对,容易知道此搭配下左手和右手手套尺码差距均为 0。
样例 2 解释
最多可以配对成功 3 副手套,搭配关系为 (l2,r1),(l3,r2),(l4,r3),容易知道此搭配下,手套尺码差距为 0,1,1,最大手套尺码差距为 1。
样例 3 解释
最多可以配对成功 5 副手套,最终的搭配关系为 (l3=1,r4=3),(l4=2,r3=6),(l2=6,r1=9),(l1=7,r2=11),(l5=10,r5=12),手套尺码差距分别为 2,4,3,4,2,最大手套尺码差值为 4。
数据范围
对于 20% 的数据,n=m
对于另外 50% 的数据,n,m≤500
对于 100% 的数据,1≤n,m≤100000,0≤li,ri≤109