#1706. 「THUPC 2019」不等式 / inequality

「THUPC 2019」不等式 / inequality

题目描述

时光回到 2017 年 6 月 7 日。午后,阳光正好。
现在的你,在考场中笔耕不辍。在刷刷声中,你填写着交给从前和未来的自己的答卷。
像无数次训练过的那样,你直接跳到了这张数学试卷的最后一道大题,二选一的题目直接选择了后者。快速地掠过了题目描述,紧缩的眉头渐渐放松。
「稳了。」
你一刻也不敢停留,又向你的梦想靠近了一小步。

已知两个 nn 维实向量 a=(a1,a2,,an),\vec{a}=(a_1,a_2,\dots,a_n), b=(b1,b2,,bn)\vec{b}=(b_1,b_2,\dots,b_n),定义 nn 个定义域为 R 函数 f1,f2,,fnf_1,f_2,\dots,f_n

$$f_k(x)=\sum_{i=1}^{k} {\lvert a_ix+b_i\rvert} \quad (k=1,2,\dots,n) $$

现在,对于每个 k=1,2,,nk=1,2,\dots,n,试求 fkf_kR 上的最小值。可以证明最小值一定存在。

输入格式

第一行一个整数 nn,表示向量的长度及函数的个数。

接下来两行,每行 nn 个整数,分别描述向量 a,b\vec{a},\vec{b} 的各个分量,以空格隔开。

对于所有的输入数据,都满足 $1\le n\le 5\times 10^5,\lvert a_i\rvert ,\lvert b_i\rvert <10^5$。

输出格式

输出 nn 行,第 ii 行为一个实数,表示 fif_iR 上的最小值。

输出与标准答案的绝对误差或相对误差小于 10610^{-6} 就会被算作正确。

样例

2
1 1
1 2
0.00000
1.00000

f1(x)=x+1f_1(x)=\lvert x+1\rvert,显然在 x=1x=-1 处取到最小值 00f2(x)=x+1+x+2f_2(x)=\lvert x+1\rvert +\lvert x+2\rvert,可以证明其在 [2,1][-2,-1] 中任意位置取到最小值 11

数据范围与提示

后记

后来,全国三卷的考生们又回想起了被参数方程支配的恐惧。

版权信息

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。
题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。