YJQQQAQ's Blog

题意：给n个实数，可以在任意位置加入任意大小的m个实数，希望让插入后的序列的$\sum_{i=1}^{n+m}(a[i]-a[i-1]-L)^2$最小

​$n\leq50000  m\leq10^8 |L|\leq100$

题解：

首先把式子拆开，变成 $\sum_{i=1}^{n+m}(a[i]-a[i-1])^2 - 2*a[n]*L + 2*a[1] * L + L^2 * (n+m-1)$

此时​发现后面三个东西，都不会变化（你往两边插不会使答案变小）

然后就变成了往一个序列里面插入某些数，使相邻两个数的平方和最小

我们考虑把相邻两个差为k的数中间，插入j个数，最小变成多少

显然应该均匀插入，于是这两个数对sum的贡献从k^2变成了k^2/(j+1)

我们考虑增量，发现从插入i个数，变成插入i+1个数，相当于是答案变小了k^2/(i*(i+1))

然后用一个priority_queue，记录增量，可以做到mlgn，但是显然是过不了的

最后发现可以二分最小的增量大小，判断是否存在m个比二分的增量大的增量，于是复杂度变成了n*二分次数

注意二分的精度相当恶心

同时还要注意，虽然往两边插入不会使答案变小，但是如果最后二分出来的增量小于L^2，可以向两边插入

也就是说我们二分的增量大小，最小是L^2

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>
#include <stack>
#include <vector>
#include <cmath>
using namespace std;

double L;

int n,m;

const int MAXN = 50010;
double eps = 1e-14;

int sgn(double x) {
		if (abs(x) < eps) return 0;
		if (x >= eps) return 1;
		return -1;
}
double a[MAXN];
double ans = 0;
int get_sum(double k,double x) {
		if (sgn(x - k/(double) 2.0) > 0) return 0;
		int p = sqrt(k/x + 0.5);
		p ++;
		while (sgn(k / ((double) p * (double) (p+1))  - x) < 0 && p) p --;
		return p;
}
int calc(double x) {
		int ret = 0;
		for (int i=2;i<=n;i++) {
				double k = a[i] - a[i-1];
				ret += get_sum(k*k,x);
		}
		return ret;
}

double sqr(double x) {
		return x * x;
}
int main() {

		scanf("%d%d%lf",&n,&m,&L);
		for (int i=1;i<=n;i++) scanf("%lf",&a[i]);
		for (int i=2;i<=n;i++) {
				ans += (a[i] - a[i-1] - L) * (a[i] - a[i-1] - L);
		}
		double l = L * L;
		double r = 1e9;
		if (m < 5000) eps = 1e-10;//protect from bao jing du
		while (sgn(r-l) > 0) {
				double mid = (l + r) / 2.0;
				if (calc(mid) < m) r = mid;
				else l = mid;
		}
		for (int i=2;i<=n && m;i++) {
				int p = get_sum((double) sqr(a[i] - a[i-1]),l);
				p = min(p,m);
				if (p) 
				ans = ans - sqr(a[i] - a[i-1]) + (double) sqr(a[i] - a[i-1]) / ((double) (p + 1)) + L * L * p;
				m -= p;
		}
		printf("%.3lf\n",ans);
}