题目大意
求形如
[sum_{i=1}^n |a_ix + b_i|
]
的最小值
思路
我们显然可以先把系数 (a) 提出来
于是就成了 (sum_{i=1}^n |a_i|·|x + frac{b_i}{a_i}|)
对于任意一个 (i),它的零点在 (-frac{b_i}{a_i}) 处
而我们知道整个函数的最值必然在零点处
那么取所有零点计算取最小值就可以了
(O(n^2))
其实并不需要那么高的复杂度
我们先将零点从大到小排序
然后换一个零点时,它后面的式子小于零,前面的式子大于零,用它的增量就可以 (O(1)) 计算了
注意:(a_i) 可能为零!需特别处理
(Code)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 3e5 + 5;
int n , m;
struct node{
double a , b;
}c[N + 5];
double val , ans , k1 , k2;
bool cmp(node x , node y){return x.b < y.b;}
int main()
{
freopen("spongebob.in" , "r" , stdin);
freopen("spongebob.out" , "w" , stdout);
scanf("%d" , &n);
for(register int i = 1; i <= n; i++)
{
++m;
scanf("%lf%lf" , &c[m].a , &c[m].b);
if (c[m].a == 0) {val += abs(c[m].b); --m; continue;}
c[m].b = -c[m].b / c[m].a , c[m].a = fabs(c[m].a);
}
sort(c + 1 , c + m + 1 , cmp);
for(register int i = 2; i <= m; i++) val += (c[i].b - c[1].b) * c[i].a , k1 += c[i].a;
k2 = c[1].a , ans = val;
for(register int i = 2; i <= m; i++)
{
val -= k1 * (c[i].b - c[i - 1].b);
val += k2 * (c[i].b - c[i - 1].b);
k1 -= c[i].a , k2 += c[i].a;
ans = min(ans , val);
}
printf("%lf
" , ans);
}