309752: CF1730B. Meeting on the Line
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Meeting on the Line
题意翻译
给定长为 $n$ 的序列 $x$ 和 $t$，请你求出一个 $x_0$，使得 $\max\limits_{i=1}^{n}\{t_i+|x_i-x_0|\}$ 最小，输出 $x_0$。题目描述
$ n $ people live on the coordinate line, the $ i $ -th one lives at the point $ x_i $ ( $ 1 \le i \le n $ ). They want to choose a position $ x_0 $ to meet. The $ i $ -th person will spend $ |x_i - x_0| $ minutes to get to the meeting place. Also, the $ i $ -th person needs $ t_i $ minutes to get dressed, so in total he or she needs $ t_i + |x_i - x_0| $ minutes. Here $ |y| $ denotes the absolute value of $ y $ . These people ask you to find a position $ x_0 $ that minimizes the time in which all $ n $ people can gather at the meeting place.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of test cases. Then the test cases follow. Each test case consists of three lines. The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the number of people. The second line contains $ n $ integers $ x_1, x_2, \dots, x_n $ ( $ 0 \le x_i \le 10^{8} $ ) — the positions of the people. The third line contains $ n $ integers $ t_1, t_2, \dots, t_n $ ( $ 0 \le t_i \le 10^{8} $ ), where $ t_i $ is the time $ i $ -th person needs to get dressed. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, print a single real number — the optimum position $ x_0 $ . It can be shown that the optimal position $ x_0 $ is unique. Your answer will be considered correct if its absolute or relative error does not exceed $ 10^{−6} $ . Formally, let your answer be $ a $ , the jury's answer be $ b $ . Your answer will be considered correct if $ \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说明
- In the $ 1 $ -st test case there is one person, so it is efficient to choose his or her position for the meeting place. Then he or she will get to it in $ 3 $ minutes, that he or she need to get dressed. - In the $ 2 $ -nd test case there are $ 2 $ people who don't need time to get dressed. Each of them needs one minute to get to position $ 2 $ . - In the $ 5 $ -th test case the $ 1 $ -st person needs $ 4 $ minutes to get to position $ 1 $ ( $ 4 $ minutes to get dressed and $ 0 $ minutes on the way); the $ 2 $ -nd person needs $ 2 $ minutes to get to position $ 1 $ ( $ 1 $ minute to get dressed and $ 1 $ minute on the way); the $ 3 $ -rd person needs $ 4 $ minutes to get to position $ 1 $ ( $ 2 $ minutes to get dressed and $ 2 $ minutes on the way).Input
题意翻译
给定长为 $n$ 的序列 $x$ 和 $t$，请你求出一个 $x_0$，使得 $\max\limits_{i=1}^{n}\{t_i+|x_i-x_0|\}$ 最小，输出 $x_0$。Output
**线上的相遇**
**题意翻译**
给定一个长度为 $ n $ 的序列 $ x $ 和 $ t $，请找到一个 $ x_0 $，使得 $ \max\limits_{i=1}^{n}\{t_i+|x_i-x_0|\} $ 最小，并输出 $ x_0 $。
**题目描述**
$ 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 $，使得所有人都能在最短的时间内聚集在会面地点。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ 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 $ 个测试用例中，只有一个人，因此选择他或她的位置作为会面地点是有效的。然后他或她将在 $ 3 $ 分钟内到达，这是他或她需要打扮的时间。
- 在第 $ 2 $ 个测试用例中，有两个人不需要打扮的时间。他们每个人需要一分钟到达位置 $ 2 $。
- 在第 $ 5 $ 个测试用例中，第 $ 1 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 4 $ 分钟打扮和 $ 0 $ 分钟在路上）；第 $ 2 $ 个人需要 $ 2 $ 分钟到达位置 $ 1 $（$ 1 $ 分钟打扮和 $ 1 $ 分钟在路上）；第 $ 3 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 2 $ 分钟打扮和 $ 2 $ 分钟在路上）。**线上的相遇** **题意翻译** 给定一个长度为 $ n $ 的序列 $ x $ 和 $ t $，请找到一个 $ x_0 $，使得 $ \max\limits_{i=1}^{n}\{t_i+|x_i-x_0|\} $ 最小，并输出 $ x_0 $。 **题目描述** $ 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 $，使得所有人都能在最短的时间内聚集在会面地点。 **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $ 个测试用例中，只有一个人，因此选择他或她的位置作为会面地点是有效的。然后他或她将在 $ 3 $ 分钟内到达，这是他或她需要打扮的时间。 - 在第 $ 2 $ 个测试用例中，有两个人不需要打扮的时间。他们每个人需要一分钟到达位置 $ 2 $。 - 在第 $ 5 $ 个测试用例中，第 $ 1 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 4 $ 分钟打扮和 $ 0 $ 分钟在路上）；第 $ 2 $ 个人需要 $ 2 $ 分钟到达位置 $ 1 $（$ 1 $ 分钟打扮和 $ 1 $ 分钟在路上）；第 $ 3 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 2 $ 分钟打扮和 $ 2 $ 分钟在路上）。
**题意翻译**
给定一个长度为 $ n $ 的序列 $ x $ 和 $ t $，请找到一个 $ x_0 $，使得 $ \max\limits_{i=1}^{n}\{t_i+|x_i-x_0|\} $ 最小，并输出 $ x_0 $。
**题目描述**
$ 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 $，使得所有人都能在最短的时间内聚集在会面地点。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ 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 $ 个测试用例中，只有一个人，因此选择他或她的位置作为会面地点是有效的。然后他或她将在 $ 3 $ 分钟内到达，这是他或她需要打扮的时间。
- 在第 $ 2 $ 个测试用例中，有两个人不需要打扮的时间。他们每个人需要一分钟到达位置 $ 2 $。
- 在第 $ 5 $ 个测试用例中，第 $ 1 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 4 $ 分钟打扮和 $ 0 $ 分钟在路上）；第 $ 2 $ 个人需要 $ 2 $ 分钟到达位置 $ 1 $（$ 1 $ 分钟打扮和 $ 1 $ 分钟在路上）；第 $ 3 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 2 $ 分钟打扮和 $ 2 $ 分钟在路上）。**线上的相遇** **题意翻译** 给定一个长度为 $ n $ 的序列 $ x $ 和 $ t $，请找到一个 $ x_0 $，使得 $ \max\limits_{i=1}^{n}\{t_i+|x_i-x_0|\} $ 最小，并输出 $ x_0 $。 **题目描述** $ 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 $，使得所有人都能在最短的时间内聚集在会面地点。 **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $ 个测试用例中，只有一个人，因此选择他或她的位置作为会面地点是有效的。然后他或她将在 $ 3 $ 分钟内到达，这是他或她需要打扮的时间。 - 在第 $ 2 $ 个测试用例中，有两个人不需要打扮的时间。他们每个人需要一分钟到达位置 $ 2 $。 - 在第 $ 5 $ 个测试用例中，第 $ 1 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 4 $ 分钟打扮和 $ 0 $ 分钟在路上）；第 $ 2 $ 个人需要 $ 2 $ 分钟到达位置 $ 1 $（$ 1 $ 分钟打扮和 $ 1 $ 分钟在路上）；第 $ 3 $ 个人需要 $ 4 $ 分钟到达位置 $ 1 $（$ 2 $ 分钟打扮和 $ 2 $ 分钟在路上）。