51nod 1598 方程最小值

未分类

---

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1598

题意：
给定两个长度为$n$的数组$k_i,b_i$,定义：

$$\begin{align*} f_m(x)=\sum_{i=1}^m|k_ix+b_i| \end{align*}$$
对$m=1,2,...,n$，求$min\{f_m(x)\}$.
数据范围：$1\leq n \leq 10^5,0 \leq |k_i| \leq 10^3,0\leq |b_i|\leq 10^9$.

解析：
如果$k_i<0$，使$k_i=-k_i,b_i=-b_i$.
容易知道对单一的 $y=|kx+b|$，它是直线$y=kx+b$将$y<0$的部分与$x$轴对称之后得到的曲线.
如果$k=0$,只需要特殊考虑即可.
否则存在$x_0=\frac{-b}{k}$，对$y=|kx+b|$有：

$$\begin{align*} 　y&=-kx-b &if(x<x_0) \\ 　y&=kx+b &else \end{align*}$$
显然可以知道$f_m(x)$是一个分段函数，且每段函数都是一条直线，且直线的斜率随着$x$增大而增大.
先求出所有$x_{i}=\frac{-b}{k}$，离散化，可以知道$f_m(x)$的最小值一定在$x \in \{x_{1},x_{2},...,x_{m}\}$ 中取到.

下面简略对此进行证明：
对所有的$y=k_ix+b_i$以$x_{i}=\frac{-b}{k}$从小到大排序，那么对$f_m(x)$，随着$x$从$x_{i-1}$增大到$x_{i}=\frac{-b}{k}$后，$y_i=|k_ix+b_i|$对$f_m(x)$的贡献就由$(-k_i,-b_i)$变成$(k_i,b_i)$，其中$k_i>0$，也就是$f_m(x)$的斜率变大了.
说明$f_m(x)$是一个导数单调不递减的函数，且其斜率在$x_i(1\leq i \leq m)$处不存在，其最小值在斜率由负变为正的时候取到，注意此时斜率并不存在，也就是在某个$x_i$处取到最小值.

考虑维护一个对于$k$的线段树和对于$b$的线段树，那么每加入一个新的$y_i=k_ix+b_i$，求出$x_i$离散化之后的大小$pos$，在线段树$[1,pos]$上加上二元组$(-k_i,-b_i)$，在$[pos+1,n]$上加上二元组$(k_i,b_i)$，线段树维护区间最小值，同样可以在$O(log(n))$的时间内求出最大的$id$，使$\sum_{j=1}^{id}{k_j}<0$，注意这里的$k_j$可能是负的.

对线段树只要维护区间加、区间最小值、单点查询、区间查询即可.

那么查询答案就是：

$$ans=x_{id}*\sum_{j=1}^{id}{k_j}+\sum_{j=1}^{id}{b_j}$$
总时间复杂度$O(nlogn)$.

$AC$ $code$： https://paste.ubuntu.com/p/bybKfdTtWW/