CF2229D Me When Median Problem

给定两个长度为 $n$ 的正整数数组 $a$ 和 $b$。你需要恰好执行 $n-1$ 次如下操作： - 设 $m$ 为当前 $a$ 和 $b$ 的长度（注意每次操作后它们的长度始终相等）。 - 选择一个整数 $i$（$1 \leq i < m$）： - 令 $S$ 为多重集 $\{a_i, a_{i+1}, b_i, b_{i+1}\}$。 - 将 $S$ 中的元素排序，记 $s_1 \leq s_2 \leq s_3 \leq s_4$。 - 用 $s_2$ 替换 $a_i$，用 $s_3$ 替换 $b_i$，并删除 $a_{i+1}$ 和 $b_{i+1}$。更形式化地，$a$ 被替换为 $[a_1, a_2, \ldots, a_{i-1}, s_2, a_{i+2}, \ldots, a_m]$，$b$ 被替换为 $[b_1, b_2, \ldots, b_{i-1}, s_3, b_{i+2}, \ldots, b_m]$。 经过所有操作后，$a$ 和 $b$ 都只剩下一个元素。请你在最优操作下，求 $\min(a_1, b_1)$ 的最大可能取值。

每组测试数据包含多组测试用例。第一行为测试用例数 $t$（$1 \leq t \leq 10^4$）。 每个测试用例包含三行： 第一行一个整数 $n$（$1 \leq n \leq 10^5$），表示数组 $a$ 和 $b$ 的长度。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 2n$）。 第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$1 \leq b_i \leq 2n$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一行答案，表示 $\min(a_1, b_1)$ 能达到的最大值。

在第一个样例中，无需进行任何操作，答案即为 $\min(1, 2) = 1$。 在第二个样例中，可以执行如下操作： - 选择 $i=1$： - $S = \{2, 4, 1, 3\}$，$s_1 = 1$，$s_2 = 2$，$s_3 = 3$，$s_4 = 4$ - $a = [\color{red}{2, 4}, 5] \rightarrow [\color{red}{2}, 5]$ - $b = [\color{red}{1, 3}, 6] \rightarrow [\color{red}{3}, 6]$ - 再次选择 $i=1$： - $S = \{2, 5, 3, 6\}$，$s_1 = 2$，$s_2 = 3$，$s_3 = 5$，$s_4 = 6$ - $a = [\color{red}{2, 5}] \rightarrow [\color{red}{3}]$ - $b = [\color{red}{3, 6}] \rightarrow [\color{red}{5}]$ 此时答案为 $\min(3, 5) = 3$，且可以证明这是最优结果。 由 ChatGPT 5 翻译