← 返回题目列表

Codeforces · 1730/B

B. 会议上线

中文机器翻译题面 查看原题

$$$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$$$) — 测试用例的数量。然后是测试用例。

每个测试用例由三行组成。

第一行包含一个整数 $$$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

7
1
0
3
2
3 1
0 0
2
1 4
0 0
3
1 2 3
0 0 0
3
1 2 3
4 1 2
3
3 3 3
5 3 3
6
5 4 7 2 10 4
3 2 5 1 4 6

输出 #1

0
2
2.5
2
1
3
6

注意

- 在 $$$1$$$-st 测试用例中只有一个人,因此选择他或她的会议地点位置是有效的。然后他或她将在 $$$3$$$ 分钟内完成,他或她需要穿好衣服。
- 在 $$$2$$$-nd 测试用例中,有 $$$2$$$ 人不需要时间穿衣服。他们每个人都需要一分钟才能到达 $$$2$$$ 位置。
- 在第 $$$5$$$ 测试用例中,第 $$$1$$$ 人需要 $$$4$$$ 分钟才能到达 $$$1$$$ 位置($$$4$$$ 分钟穿好衣服,$$$0$$$ 分钟在路上); $$$2$$$-nd 人需要 $$$2$$$ 分钟到达位置 $$$1$$$($$$1$$$ 分钟穿好衣服,$$$1$$$ 分钟在路上);第 $$$3$$$ 人需要 $$$4$$$ 分钟才能到达 $$$1$$$ 位置($$$2$$$ 分钟穿好衣服,$$$2$$$ 分钟在路上)。