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

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: WAAutoMaton

题目描述

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

已知两个 n 维实向量 \vec{a}=(a_1,a_2,\dots,a_n), \vec{b}=(b_1,b_2,\dots,b_n) ,定义 n 个定义域为 函数 f_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,\dots,n ,试求 f_k 上的最小值。可以证明最小值一定存在。

输入格式

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

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

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

输出格式

输出 n 行,第 i 行为一个实数,表示 f_i 上的最小值。

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

样例

样例输入 1
2
1 1
1 2
样例输出 1
0.00000
1.00000
样例说明 1

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

数据范围与提示

后记

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

版权信息

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