[THUPC2019]不等式/[51Nod1598]方程最小值
题目大意：
给定(a_{1sim n})和(b_{1sim n})，令(f_k(x)=sum_{i=1}^k|a_ix+b_i|)。对于所有(k=1sim n)，求(f_k)在(mathbb{R})中的最小值。
(1le nle 5 imes10^5,|a_i|,|b_i|<10^5)
思路：
[sum_{i=1}^k|a_ix+b_i|=sum_{i=1}^k|a_i||x+frac{b_i}{a_i}|
]
画在数轴上就是在(-frac{b_i}{a_i})（即零点）的位置有(|a_i|)个点。要找到一个位置(x)，使得(x)到所有点的距离之和最小。
根据小学奥数的那套理论，(x)就是所有零点的加权中位数。我们可以用一个大根堆、一个小根堆来维护所有的零点，并求出中位数。
考虑函数加上绝对值后，(a_i)实际的符号。对于(-frac{b_i}{a_i}<x)的函数来说，(a_i>0)；反之(a_i<0)。因此我们可以在对两个堆中的元素分别维护考虑绝对值后(a_i,b_i)之和。即可求出最终(f_k(x))的最小值。
时间复杂度(mathcal O(nlog n))。
源代码：
#include<queue>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<algorithm>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
const int N=5e5+1;
using int64=long long;
using Node=std::pair<double,int>;
std::priority_queue<Node,std::vector<Node>,std::greater<Node>> q1;//small
std::priority_queue<Node,std::vector<Node>,std::less<Node>> q2;//big
int64 s1,s2,a1,a2,b1,b2,a[N],b[N];
double o[N];
int main() {
const int n=getint();
for(register int i=1;i<=n;i++) a[i]=getint();
for(register int i=1;i<=n;i++) b[i]=getint();
for(register int i=1;i<=n;i++) {
if(a[i]!=0) {
o[i]=-1.*b[i]/a[i];
if(s1&&o[i]>q1.top().first) {
q1.push(std::make_pair(o[i],i));
if(a[i]>0) a[i]=-a[i],b[i]=-b[i];
a1+=a[i]; b1+=b[i];
s1+=std::abs(a[i]);
} else {
q2.push(std::make_pair(o[i],i));
if(a[i]<0) a[i]=-a[i],b[i]=-b[i];
a2+=a[i]; b2+=b[i];
s2+=std::abs(a[i]);
}
} else {
b1+=std::abs(b[i]);
}
while(s1>s2) {
q2.push(q1.top());
const int i=q1.top().second;
a1-=a[i]; b1-=b[i];
s1-=std::abs(a[i]);
a[i]=-a[i]; b[i]=-b[i];
a2+=a[i]; b2+=b[i];
s2+=std::abs(a[i]);
q1.pop();
}
while(s2>s1) {
q1.push(q2.top());
const int i=q2.top().second;
a2-=a[i]; b2-=b[i];
s2-=std::abs(a[i]);
a[i]=-a[i]; b[i]=-b[i];
a1+=a[i]; b1+=b[i];
s1+=std::abs(a[i]);
q2.pop();
}
const double x=s1?q1.top().first:0;
printf("%.7f
",a1*x+b1+a2*x+b2);
}
return 0;
}