我与中位数题AI (CI翻译)
You are given two arrays of positive integers $a$ and $b$, both of length $n$. You will perform the following operation exactly $n - 1$ times:
你有两个长度均为 $n$ 的正整数数组 $a$ 和 $b$。你需要恰好执行 $n - 1$ 次以下操作：AI (CI翻译)
- let
$m$be the current length of$a$and$b$, note that the lengths will always be equal. - select an integer
$i$($1 \le i \lt m$): - let
$S$be the multiset$\{a_i, a_{i + 1}, b_i, b_{i + 1}\}$- sort the elements of
$S$such that$s_1 \le s_2 \le s_3 \le s_4$. - now replace
$a_i, a_{i + 1}$with$s_2$and$b_i, b_{i + 1}$with$s_3$. More formally, replace$a$with$[a_1,a_2,\ldots,a_{i - 1},s_2,a_{i + 2},\ldots,a_m]$, and replace$b$with$[b_1,b_2,\ldots,b_{i - 1},s_3,b_{i + 2},\ldots,b_m]$.
- sort the elements of
- 设当前
$a$和$b$的长度为$m$，注意两者的长度始终相等。 - 选择一个整数
$i$（$1 \le i \lt m$）： - 设多重集合
$S$为$\{a_i, a_{i + 1}, b_i, b_{i + 1}\}$。- 将
$S$中的元素排序，使得$s_1 \le s_2 \le s_3 \le s_4$。 - 现在将
$a_i, a_{i + 1}$替换为$s_2$，将$b_i, b_{i + 1}$替换为$s_3$。更形式化地说，将$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]$。
- 将
After performing all operations, there will be exactly $1$ element remaining in both $a$ and $b$. Determine the maximum value of $\min(a_1, b_1)$ attainable if you perform operations optimally.
执行完所有操作后，$a$ 和 $b$ 中都将恰好剩下 $1$ 个元素。请确定通过最优地执行操作，$\min(a_1, b_1)$ 能达到的最大值。AI (CI翻译)
Input
输入格式
AI (CI翻译)Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。AI (CI翻译)
The first line of each testcase contains an integer $n$ ($1 \le n \le 10^5$) — the length of the arrays $a$ and $b$.
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）——数组的长度。AI (CI翻译)
The second line of each testcase contains $n$ integers $a_1,a_2,\ldots,a_{n}$ ($1 \le a_i \le 2 \cdot n$).
每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_{n}$（$1 \le a_i \le 2 \cdot n$）。AI (CI翻译)
The third line of each testcase contains $n$ integers $b_1,b_2,\ldots,b_{n}$ ($1 \le b_i \le 2 \cdot n$).
每个测试用例的第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_{n}$（$1 \le b_i \le 2 \cdot n$）。AI (CI翻译)
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
保证所有测试用例的 $n$ 之和不超过 $10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each testcase, output the maximum value of $\min(a_1,b_1)$ attainable.
对于每个测试用例，输出 $\min(a_1,b_1)$ 能达到的最大值。AI (CI翻译)
Note
说明
AI (CI翻译)In the first example, we do not need to perform any operations, so the answer is just $\min(1, 2)$ which is $1$.
在第一个样例中，我们不需要执行任何操作，因此答案就是 $\min(1, 2)$，即 $1$。AI (CI翻译)
For the second example, we can do the following sequence of moves:
对于第二个样例，我们可以执行如下操作序列：AI (CI翻译)
- select
$i = 1$and then: $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]$
- select
$i = 1$and then $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}]$
- 选择
$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}]$
The answer is then $\min(3, 5)$ which is $3$, it can be proven that this is optimal.
因此答案为 $\min(3, 5)$，即 $3$。可以证明这是最优的。AI (CI翻译)
样例
6
1
1
2
3
2 4 5
1 3 6
4
7 5 4 8
4 6 7 8
8
8 7 13 11 1 10 4 5
11 11 12 8 9 2 3 13
9
16 1 9 12 5 18 10 10 16
14 6 7 11 12 17 18 3 17
6
3 6 12 4 10 12
2 3 2 7 8 9
1
3
6
8
14
8
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。