B. 美味餐食 详细题解

题目核心理解

有 $n$ 道前菜，辣度分别为 $a_i$；有 $n$ 道主菜，辣度分别为 $b_i$。 需要将前菜与主菜两两完美配对，每道菜恰好使用一次。

定义一餐的魅力值为前菜与主菜辣度的绝对差值 $|a_i - b_j|$。 要求最大化所有配对中最小的魅力值，输出这个最大可能值。

---

核心思路

1. 关键性质

• 先将数组 $a$、$b$ 从小到大排序。
• 最优配对一定可以表示为某种两段式交叉匹配： 选取一个分割位置 $t$，把最小的 $t$ 个 $a$ 配最大的 $t$ 个 $b$， 剩下较大的 $n-t$ 个 $a$ 配最小的 $n-t$ 个 $b$。
• 枚举所有可能的 $t$，计算每种配对下的最小魅力值，再取最大值即为答案。

2. 匹配规则

对每个枚举的 $t$（$0\le t\le n$）：

• 前 $t$ 个 $a_i$ 与 $b$ 中最后 $t$ 个匹配，即 $a_i \leftrightarrow b_{i+(n-t)}$；
• 后 $n-t$ 个 $a_i$ 与 $b$ 中前 $n-t$ 个匹配，即 $a_i \leftrightarrow b_{i-t}$。

3. 最优性依据

根据排序不等式与排列引理，任何合法且满足最小魅力 $\ge k$ 的方案，都可以转化为上述两段式结构，因此只需枚举 $t$ 即可覆盖所有最优可能。

---

算法流程

1. 对每组测试用例，读入 $n$、数组 $a$、数组 $b$；
2. 将 $a$、$b$ 分别升序排序；
3. 枚举 $t$ 从 $0$ 到 $n$：
   • 按上述规则完成配对；
   • 计算当前所有配对中最小魅力值；
4. 在所有 $t$ 对应的最小值中，取最大值作为答案输出。

---

公式与复杂度分析

对给定 $t$，匹配规则：

$$j= \begin{cases} i+(n-t) & 0\le i<t \\ i-t & t\le i<n \end{cases} $$

魅力值：

$$val = |a_i - b_j|$$

复杂度

• 排序：$O(n\log n)$
• 枚举 $t$ 并遍历检查：$O(n^2)$
• 总时间复杂度：$O(n^2)$

满足题目限制：所有测试用例的 $\sum n^2 \le 25\cdot 10^6$，可在时限内轻松通过。