description 对于给定的 { a i } , { b i } \{a_i\},\{b_i\} {ai​},{bi​}，定义 f k ( x ) = ∑ i = 1 k abs ⁡ ( a i x + b i ) f_k(x)=\begin{matrix}\sum_{i=1}^k\end{matrix}\operatorname{abs}(a_ix+b_i) fk​(x)=∑i=1k​​abs(ai​x+bi​)

对于每一个 k k k，求 f k ( x ) f_k(x) fk​(x)的最小值

solution 首先考虑 a i = 1 a_i=1 ai​=1的时候，也就是我们要求 min ⁡ { ∑ ∣ x + b i ∣ } \min\{\sum |x+b_i|\} min{∑∣x+bi​∣} ∣ x + b i ∣ |x+b_i| ∣x+bi​∣的几何意义就是在数轴上， x x x到 − b i -b_i −bi​这个点的距离 那么根据初一数学的芝士， x x x取所有 − b i -b_i −bi​的时候可以取到最小值

那么当 a i = − 1 a_i=-1 ai​=−1的时候呢？每一个式子变成了 ∣ − x + b i ∣ = ∣ x − b i ∣ |-x+b_i|=|x-b_i| ∣−x+bi​∣=∣x−bi​∣，也就是数轴上 x x x到 b i b_i bi​的距离 这样的话我们还是把一个式子对应成了一个点

当 ∣ a i ∣ ≠ 1 |a_i|\neq1 ∣ai​∣​=1时，也就是式子是最基本的 ∣ a i x + b i ∣ |a_ix+b_i| ∣ai​x+bi​∣时，我们转化一下，变成 ∣ a i ∣ ∣ x + b i a i ∣ |a_i||x+\frac{b_i}{a_i}| ∣ai​∣∣x+ai​bi​​∣，注意外面 a i a_i ai​的绝对值不能丢 这个式子相当于 a i a_i ai​倍的 x x x到 − b i a i -\frac{b_i}{a_i} −ai​bi​​的距离，相当于把它转化成了 a i a_i ai​个点

这样的话类比 a i = 1 a_i=1 ai​=1的时候的方法，利用一个线段树维护这道题就轻松解决了

注意因为坐标可能出现分数，所以我们需要先算出每个式子转化成的坐标离散化之后再进行建树

细节还是挺多的，注意需要考虑 a i = 0 a_i=0 ai​=0的情况

code