题意：

给出一个n个数字的数列a，两个数之间的差异值定义为$max\{|A_i-A_{i-1} |,2≤i≤n\}$。现在要插入m个数，可以插在最前面，中间，最后面，问插入后的最小的差异值为多少。

思路：

容易想到可以二分答案，知道答案后每个坑位可以填哪些数字就可以确定了。

匹配：

考虑二分图匹配的思路。m个数字和n+1个坑位进行匹配，这里会发现又问题，因为如果有个坑位不放数字，这样进行匹配的话不能看出来这个不放数字的坑位前后数字相差本身是否满足条件。所以可以引入几个假数字，让他们匹配不插数字就满足条件的坑位。再进行匹配。

这里注意vis和link的数组大小，应该是右列的编号。

网络流：

n+1 中 A 个必填坑位、B 个不必填坑位与 m 个广告匹配，源点拆点，[S->S1-> 必填坑位]限流 A，[S->S2->不必填坑位]限流 B，check 条件最大流=m。

（做完网络流24题后再来看看吧）

代码：

#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n,m;
int a[210],b[210];
vector<int>v[510];//每个广告可以匹配的间隔
bool vis[510];
int link[510];//右列中与之匹配的左边的
bool judgee(int id)
{
    for(int i=0;i<v[id].size();i++)
    {
        int temp=v[id][i];
        if(!vis[temp])
        {
            vis[temp]=true;
            if(link[temp]==-1||judgee(link[temp]))
            {
                link[temp]=id;
                return true;
            }
        }
    }
    return false;
}
int maxmatch()
{
    int num=0;
    for(int i=1;i<=n+1;i++)
    {
        memset(vis,0,sizeof(vis));
        if(judgee(i))
            num++;
    }
    return num;
}
bool judge(int x)
{
    memset(link,-1,sizeof(link));
    for(int i=1;i<=n+1;i++)
        v[i].clear();
    //1~m表示真广告，m+1~n+1表示假广告，n+2~2*n+2表示坑位
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(abs(b[i]-a[j])<=x&&abs(b[i]-a[j+1])<=x)
                v[i].push_back(n+j+2);
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(abs(b[i]-a[1])<=x)
            v[i].push_back(n+2);
        if(abs(b[i]-a[n])<=x)
            v[i].push_back(2*n+2);
    }
    for(int i=m+1;i<=n+1;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(abs(a[j]-a[j+1])<=x)
                v[i].push_back(n+j+2);
        }
    }
    for(int i=m+1;i<=n+1;i++)
    {
        v[i].push_back(n+2);
        v[i].push_back(2*n+2);
    }
    /*if(x==2)
    {
        for(int i=1;i<=n+1;i++)
        {
            printf("%d:",i);
            for(int j=0;j<v[i].size();j++)
                printf("%d ",v[i][j]);
            printf("\n");
        }
    }*/
    int ans=maxmatch();
    //printf("%d\n",ans);
    if(ans==n+1)return true;
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=m;i++)
            scanf("%d",&b[i]);
        int l=0,r=1e9,ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(judge(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}