已知长度为 \(n\) 的三个两个实数序列 \(A, B, X\)，定义 \(n\) 个定义域为 \(\R\) 的函数 \(f_1, f_2, \cdots, f_n\)。
其中：
\[f_k(x) = \sum_{i = 1}^k |a_i (x - x_i) + b_i| \]现在，对于每一个 \(k = 1, 2, \cdots, n\)，求 \(f_k\) 的最小值。
可以证明，最小值一定存在。
\(n \le 5e5, |a_i|, |b_i| \le 1e9\)。
精度采用 SPJ
恋爱入门教学
题目背景
hf 学会了说唱，夺得了中国第一男高的称号，迷倒了万千迷妹收获了大笔的金钱。
他广撒网广交友，交到了许多卡哇伊的 npy，可是麻烦随之而来。
题目描述
每一个 npy 对 hf 都有一个好感度 \(Favorbility_i\)（下文简记为 \(F_i\)）。而 hf 秉持着公平的原则，对于每一个 npy 的好感度 \(f\) 是一样的。于是，好感的不对等会造成一定的麻烦。
每一个 npy 都有一个麻烦率 \(Troublesome_i\)（下文简记为 \(T_i\)），如果是纠缠，那么 \(T_i\) 为正，如果是冷漠，则 \(T_i\) 为负。或许可能是真爱，有的 npy 的 \(T_i\) 为 \(0\)。
但是与每一个 npy 相处会有一个基础的麻烦度 \(B_i\)，由于也可能是帮助，所以 \(B_i\) 可能小于零。
hf 为了不让自己爆炸，所以想要最小化 hf 的麻烦度。
由于朋友是一个一个交的，所以他每交到一个 npy 就需要调整自己的 \(f\) 以减少麻烦。
形式化来说，就是对于 \(k = 1, 2, \cdots n\)，最小化：
\[\sum_{i = 1}^k |T_i(F_i - f) + B_i| \]输入格式
第一行一个数 \(n\) 表示 npy 的总个数。
接下来 \(n\) 行，每行三个数 \(T_i, F_i, B_i\)。
含义见题目描述
输出格式
一行 \(n\) 个数，保留到 \(6\) 位小数，误差在 \(10^{-6}\) 以内则视为正确。
标签：入门,一个,题解,cdots,恋爱,npy,麻烦,hf,好感度 From： https://www.cnblogs.com/jeefy/p/17607843.html