2019.9.7 海绵宝宝

2019.9.7 24OJ#11 海绵宝宝

题目：给定若干a_i和b_i，计算x取何值时，$min(sum_{i=1}^{n}|{a_{i}x+b_{i}}|)$

题解：

算法一：对于|a₁x+b₁|+|a₂x+b₂|，去掉绝对值的形式都是ax+b，所以在整个区间上单调，带入区间两个端点，复杂度O(1)，35分

算法二：扩展到三个绝对值相加，50分

算法三：

可以发现，上式中计算一个x 对应的值是$O(n) $的。结合一些数学知识，可知若提出每一个式子的“零点”——当$a_{i}x+b_{i}=0$ 时对应的$x = x_{0}$，则在x 从x₀左侧跨越到右侧时，该项的贡献变为原来的相反数。整个式子共可以提取出n 个“零点”，将数轴划分成不超过n + 1 个区间。考虑当x = ??1 时，整个式子可以将绝对值符号拆掉，拆掉绝对值符号后合并可得一个形似a′x+b′的式子。将x 向右移，每跨过一个“零点”就会导致这个“零点”对应的项贡献取反，可以O(1) 计算出新的a′,b′ 系数。

而在每两个相邻的“零点”所夹区间内，a′x + b′ 为单调函数，所以极值只可能取在区间端点处，此时已经知道了整个式子的总表达，可以O(1) 算出。在每个“零点”处花费O(1) 的时间计算，共O(n) 个“零点”，将零点排序复杂度O(n log n)。

总复杂度O(n log n)，期望得分100。

算法四：

不难发现，形似$a_{i}x+b_{i}$的函数是一个下凸函数，而这些下凸函数的和仍然是一个下凸函数。
接下来爬山、三分??您爱咋整咋整。
复杂度O(n log n)，期望得分100。

附

关于为什么这些下凸函数的和仍然是一个下凸函数

考虑对于所有的i，若a_i < 0，都将a_i，b_i 取相反数（根据绝对值的定义，绝对值内取相反数，值不

变），则所有的a_i 都不为负
将所有的项都按照函数的形式在平面上画出来，是一个形似V 的图像。
可以考虑取x =$-infty$?，此时所有的函数都呈下降趋势，且斜率为$sum_{i=1}^{n}a_{i}$。
不断将x 向右移，每当越过一个??$-frac{b_{i}}{a_{i}}$，这一项对斜率的贡献就会从-??a_i 变为+a_i，斜率总体变大。
在x 从$-infty$向$infty$移动的过程中，斜率单调不降，也即这个总函数整体下凸。

?

下凸函数：函数具有如下性质：

$f(frac{x_{1}+x_{2}}{2} )leq frac{1}{2}(f(x_{1})+f(x_{2}))$

符号相反就是上凸函数