#P11854. [CSP-J2022 山东] 宴会

[CSP-J2022 山东] 宴会

题目背景

受疫情影响,山东省取消了 CSP-J 2022 认证活动,并于次年三月重新命题,在省内补办比赛。

题目描述

今人不见古时月,今月曾经照古人。梦回长安,大唐风华,十里长安花,一日看尽。

唐长安城是当时世界上规模最大、建筑最宏伟、规划布局最为规范化的一座都城。其营建制度规划布局的特点是规模空前、创设皇城、三城层环、六坡利用、布局对称、街衢宽阔、坊 里齐整、形制划一、渠水纵横、绿荫蔽城、郊环祀坛。而所谓的十里长安街,位于长安城的中轴线上,即唐长安城的朱雀大街,又称承天门大街。唐朝官员们住在各个“坊”里,上朝下朝都需要通过朱雀大街。

为了保持各大家族的联系和友谊,各官员往往会每月办一次宴会。为了方便描述,我们把朱雀大街看成一个数轴,各官员所居住的“坊”缩略为数轴上的一个坐标点。大家决定选一处地点(该地点是数轴上的某一个点,不一定坐标点)办宴会。由于唐朝宵禁严格,大家又都希望交流时间尽可能长,因此想要使宴会开始时间尽可能早。又因为大唐注重礼仪,因此,参加宴会的官员会花一定时间盛装打扮过后才前往宴会地点(不一定是坐标点)。

更具体地,一条纵向的街道上(相当于一维坐标)有 nn 个人居住,其中第 ii 个人居住在 xix_{i} (非负整数)位置(坐标点)上。每月他们会选择在 x0x_{0}(数轴上的某一个点,不一定坐标点)出举办宴会。

已知第 ii 个人从 xix_{i} 出发前往宴会地点 x0x_{0} 处需要花费 xix0\left|x_{i}-x_{0}\right| 的时间,另外,他还需要花费 tit_{i} 的时间进行打扮,换言之,他共需要花费 xix0+ti\left|x_{i}-x_{0}\right|+t_{i} 的时间到达宴会举办处。

假设初始时刻为 00。这 nn 个人开始打扮和出发前往宴会处,他们想要使得宴会的开始时间尽可能早,于是向你求助,请你帮助他们确定好最优的宴会举办地点 x0x_{0}

注:xix0\left|x_{i}-x_{0}\right| 表示 xix_{i}x0x_{0} 之差的绝对值,且题目中 nn 个人的居住地点坐标均为整数。

输入格式

第一行一个正整数 TT,表示测试数据的组数。

接下来对于每组测试数据(注意:每组测试数据有 33 行数据,以下共 3×T3\times T 行数据):

第一行一个正整数 nn,表示总官员人数。

第二行共 nn 个非负整数 x1,x2,,xnx_{1},x_{2},\dots,x_{n} 分别表示这 nn 个人在数轴上的坐标。

第三行共 nn 个非负整数 t1,t2,,tnt_{1},t_{2},\dots,t_{n} 分别表示这 nn 个人出发前的打扮时间。

输出格式

共输出 TT 行数据,对于每组测试数据,输出一行一个实数(如果是整数按整数输出,如果有小数,保留 11 位小数输出),表示使宴会开始时间最早的最优举办地点坐标 x0x_{0}。(很显然,x0x_{0} 都是唯一的)

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
0
2
2.5
2
1
3
6

提示

样例说明

初始时刻为 00

对于第一组测试数据只有 11 个人,坐标为 00,打扮时间为 33,很显然 x0x_{0} 就定在坐标 00 处,使得宴会开始时间为 33 且最早。

对于第二组测试数据有 22 个人,坐标分别为 3311,打扮时间均为 00,很显然 x0x_{0} 定在坐标 22 处,使得宴会开始时间为 11 且最早。

对于第三组测试数据有 22 个人,坐标分别为 1144,打扮时间均为 00,很显然 x0x_{0} 定在坐标 2.52.5 处,使得宴会开始时间为 1.51.5 且最早。

数据范围

对于 30%30\% 的数据,T=1,n100,0xi,ti1000T=1,n\le100,0\le x_{i},t_{i}\le1000

对于 60%60\% 的数据,n104,0xi,ti105n\le10^{4},0\le x_{i},t_{i}\le10^{5}

对于 100%100\% 的数据,$1\le T\le10^{3},n\le10^{5},0\le x_{i},t_{i}\le10^{8}$,且保证所有测试数据的 nn 加起来不超过 2×1052\times10^{5}