CF1730B Meeting on the Line

有 $n$ 个人住在数轴上，第 $i$ 个人住在点 $x_i$ 上（$1 \le i \le n$）。他们想选择一个位置 $x_0$ 作为集合点。第 $i$ 个人需要 $|x_i - x_0|$ 分钟才能到达集合点。此外，第 $i$ 个人还需要 $t_i$ 分钟来穿衣服，所以他（她）总共需要 $t_i + |x_i - x_0|$ 分钟。 这里 $|y|$ 表示 $y$ 的绝对值。 这些人请你帮忙找到一个位置 $x_0$，使得所有 $n$ 个人都能在最短的时间内到达集合点。

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据包含三行。 第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示人数。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$0 \le x_i \le 10^{8}$），表示每个人的位置。 第三行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$（$0 \le t_i \le 10^{8}$），其中 $t_i$ 表示第 $i$ 个人穿衣服所需的时间。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个实数，表示最优的集合点位置 $x_0$。可以证明最优位置 $x_0$ 是唯一的。 如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。形式化地说，设你的答案为 $a$，标准答案为 $b$，当 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 时，视为正确。

- 在第 $1$ 个测试用例中，只有一个人，因此选择他（她）的位置作为集合点最优。他（她）到达集合点的时间就是穿衣服的 $3$ 分钟。 - 在第 $2$ 个测试用例中，有 $2$ 个人且都不需要穿衣服时间。每个人到达位置 $2$ 需要 $1$ 分钟。 - 在第 $5$ 个测试用例中，第 $1$ 个人到达位置 $1$ 需要 $4$ 分钟（$4$ 分钟穿衣服，$0$ 分钟路程）；第 $2$ 个人到达位置 $1$ 需要 $2$ 分钟（$1$ 分钟穿衣服，$1$ 分钟路程）；第 $3$ 个人到达位置 $1$ 需要 $4$ 分钟（$2$ 分钟穿衣服，$2$ 分钟路程）。 由 ChatGPT 4.1 翻译