C++11(clang++ 3.9) 解法, 执行用时: 786ms, 内存消耗: 608K, 提交时间: 2018-04-15 15:54:33

#include<bits/stdc++.h>
using namespace std;
int t,n,m,i,j,l,r,mid,a[205],b[205],d[205][205],c[205];
bool v[205];
int A(int x)
{
	if(x<0)return -x;
	return x;
}
bool dfs(int x)
{
	for(int i=1;i<=n;i++)if(!v[i]&&d[x][i]<=mid)
	{
		v[i]=1;
		if(!c[i]||dfs(c[i]))
		{
			c[i]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)scanf("%d",a+i);
		for(i=1;i<=m;i++)
		{
			scanf("%d",b+i);
			d[i][1]=A(b[i]-a[1]);
			for(j=1;j<n;j++)d[i][j+1]=max(A(b[i]-a[j]),A(b[i]-a[j+1]));
			d[i][n+1]=A(b[i]-a[n]);
		}
		for(;i<=n+1;i++)
		{
			d[i][1]=0;
			for(j=1;j<n;j++)d[i][j+1]=A(a[j+1]-a[j]);
			d[i][n+1]=0;
		}
		n++;
		l=0;
		r=1000000000;
		while(l+1<r)
		{
			mid=l+r>>1;
			fill(c+1,c+n+1,0);
			for(i=1;i<=n;i++)
			{
				fill(v+1,v+n+1,0);
				if(!dfs(i))break;
			}
			if(i>n)r=mid;
			else l=mid;
		}
		cout<<r<<endl;
	}
	return 0;
}