2019.9.7 24#11 海绵宝宝
题目：给定若干ai和bi，计算x取何值时，$min(sum_{i=1}^{n}|{a_{i}x+b_{i}}|)$
题解：
算法一：对于|a1x+b1|+|a2x+b2|，去掉绝对值的形式都是$ax+b$，所以在整个区间上单调，带入区间两个端点，复杂度O(1)，35分
算法二：扩展到三个绝对值相加，50分
算法三：
可以发现，上式中计算一个x 对应的值是$O(n) $的。结合一些数学知识，可知若提出每一个式子的“零点”——当$a_{i}x+b_{i}=0$ 时对应的$x = x_{0}$，则在$x $从x0左侧跨越到右侧时，该项的贡献变为原来的相反数。整个式子共可以提取出n 个“零点”，将数轴划分成不超过n + 1 个区间。考虑当x =$-infty$ 时，整个式子可以将绝对值符号拆掉，拆掉绝对值符号后合并可得一个形似$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，若ai < 0，都将ai，bi 取相反数（根据绝对值的定义，绝对值内取相反数，值不
变），则所有的ai 都不为负
将所有的项都按照函数的形式在平面上画出来，是一个形似V 的图像。
可以考虑取x =$-infty$ ，此时所有的函数都呈下降趋势，且斜率为$sum_{i=1}^{n}a_{i}$。
不断将x 向右移，每当越过一个$-frac{b_{i}}{a_{i}}$，这一项对斜率的贡献就会从-ai 变为+ai，斜率总体变大。
在x 从$-infty$向$infty$移动的过程中，斜率单调不降，也即这个总函数整体下凸。
下凸函数：函数具有如下性质：
$f(frac{x_{1}+x_{2}}{2} )leq frac{f(x_{1})+f(x_{2})}{2}$
符号相反就是上凸函数
#include <cstdio> #include <algorithm> #include <cmath> #define ll long long using namespace std; double suma,sumb; int n; double ans; bool cmp(double x,double y){ return x>y; } int main( ){ scanf("%d",&n); int x[3][n]; double res[n+5]; for(int i=1;i<=n;i++){ scanf("%d%d",&x[1][i],&x[2][i]); } for(int i=1;i<=n;i++){ if(x[1][i]<0){ x[1][i]=-x[1][i],x[2][i]=-x[2][i]; } suma+=x[1][i],sumb+=x[2][i]; res[i]=double(-x[2][i])/double(x[1][i]); //? } // for(int i=1;i<=n;i++){ // res[i]=double(-x[2][i])/double(x[1][i]); // } sort(res+1,res+n+1,cmp); //printf("%lf",res[1]); for(int i=1;i<=n;i++){ if(i>1) ans=min(ans,res[i]*suma+sumb); else ans=res[i]*suma+sumb; suma-=2*x[1][i],sumb-=2*x[2][i]; } printf("%lf",ans); return 0; }