Charming Meals

题面翻译

捷克菜有 $n$ 道开胃菜和 $n$ 道主菜。开胃菜的辣度为 $a_i$ ，主菜的辣度为 $b_i$ 。

一顿典型的捷克餐正好由一道开胃菜和一道主菜组成。您想把 $n$ 道开胃菜和 $n$ 道主菜搭配成 $n$ 餐，每道开胃菜和每道主菜正好包含在一餐中。

您的餐点应该给食客带来惊喜，因此您希望同一餐点的两个部分的辣度尽可能不同。一餐的魅力在于开胃菜的辣度和主菜的辣度之间的差异（绝对值）。因此，由辣度为 $x$ 的开胃菜和辣度为 $y$ 的主菜组成的一餐的魅力等于 $|x-y|$ 。

您希望最大化所得到的 $n$ 餐点的最小魅力值。最小魅力值的最大值是多少？

题目描述

The Czech cuisine features $ n $ appetizers and $ n $ main dishes. The $ i $ -th appetizer has spiciness $ a_i $ , and the $ i $ -th main dish has spiciness $ b_i $ .

A typical Czech meal consists of exactly one appetizer and one main dish. You want to pair up the $ n $ appetizers and $ n $ main dishes into $ n $ meals with each appetizer and each main dish being included in exactly one meal.

Your meals shall surprise the diners, so you want the spiciness levels of the two parts of the same meal to be as different as possible. The charm of a meal is the difference (in absolute value) between the spiciness of the appetizer and the spiciness of the main dish. So, a meal consisting of an appetizer with spiciness $ x $ and a main dish with spiciness $ y $ has charm equal to $ |x-y| $ .

You want to maximize the minimum charm of the resulting $ n $ meals. What is the largest possible value of the minimum charm that you can achieve?

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1\le t\le 1\,000 $ ) — the number of test cases. The descriptions of the $ t $ test cases follow.

The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 5\,000 $ ) —the number of appetizers and main dishes.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^{9} $ ) — the spicinesses of the $ n $ appetizers.

The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 0 \leq b_i \leq 10^{9} $ ) — the spicinesses of the $ n $ main dishes.

It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 25\cdot 10^6 $ .

输出格式

For each test case, print the largest possible value of the minimum charm you can achieve.

样例 #1

样例输入 #1

4
3
0 0 0
1000000000 1000000000 1000000000
5
1 2 3 4 5
1 2 3 4 5
6
0 0 0 100 100 100
100 100 100 0 0 0
7
14 25 62 74 86 95 12
51 62 71 72 92 20 84

样例输出 #1

1000000000
2
100
30

提示

In the first test case, no matter how you pair up the appetizers with the main dishes, each meal will have an appetizer with spiciness $ 0 $ and a main dish with spiciness $ 1000000000 $ , so the charm of each meal will be $ 1000000000 $ .

In the second test case, one optimal way to pair up appetizers and main dishes is: $ (1, 5) $ , $ (2, 4) $ , $ (3, 1) $ , $ (4, 2) $ , $ (5, 3) $ . The corresponding meals have charms: $ 4 $ , $ 2 $ , $ 2 $ , $ 2 $ , $ 2 $ . The resulting minimum charm is $ 2 $ .

In the third test case, one way to maximize the minimum charm is to pair up the three appetizers with spiciness $ 0 $ with the three main dishes with spiciness $ 100 $ , and the three appetizers with spiciness $ 100 $ with the three main dishes with spiciness $ 0 $ . Doing so, the charm of each meal will be exactly $ 100 $ .

有一些题看着像二分，其实不是，这题是贪心，由于数据比较小，可以枚举每一个断点，b在断点左边的匹配a右边的，断点右边的b匹配a左边的

 const int N = 3e5+10;
int a[N], b[N];
void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    int ans = 0;
    for (int k = 1; k <= n; k++)
    {
        int mmin = 1e18;
        for (int i = 1; i <= n; i++)
        {
            if (i < k)
            {
                mmin = min(mmin, abs(b[i] - a[n - k + i + 1]));
            }
            else mmin = min(mmin, abs(b[i] - a[i - k + 1]));
        }
        ans = max(ans, mmin);
    }
    cout << ans << '\n';
}