[THUPC2019]不等式/[51Nod1598]方程最小值

题目大意：

给定\(a_{1\sim n}\)和\(b_{1\sim n}\)，令\(f_k(x)=\sum_{i=1}^k|a_ix+b_i|\)。对于所有\(k=1\sim n\)，求\(f_k\)在\(\mathbb{R}\)中的最小值。

\(1\le n\le 5\times10^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(n\log 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\n",a1*x+b1+a2*x+b2);

	}

	return 0;

}

巴特西

[THUPC2019]不等式/[51Nod1598]方程最小值

[THUPC2019]不等式/[51Nod1598]方程最小值

题目大意：

思路：

源代码：

最新文章

热门文章