（牛客多校二）J-Link with Arithmetic Progression（最小二乘法/三分）

题目：

 样例输入：

3
3
-1 0 1
3
0 0 1
13
1 1 4 5 1 4 1 9 1 9 8 1 0

0.000000000000000
0.166666666666667
129.225274725274716

题意：给定一个数列a，将其修改为一个等差数列b，代价为,求最小代价。

这道题目其实有三种思路：

（1）三分套三分，我们先三分公差d，然后再三分首项a0，这样就能够求得答案。

（2）三分，我们直接三分公差d，设首项是x，然后列出代价表达式发现是一个二次函数，直接O（1）对其进行求值即可

（3）直接用最小二乘法来进行求解

第一种方法比较简单，我就不多说了，下面说一下第二种做法和第三种做法

第二种做法：我们三分公差d，也就是说假设我们现在已经知道了公差d，设首项是x，那么第i项是（i-1）*d+x，那么第i个数的代价就是(x+(i-1)*d-a[i])*(x+(i-1)*d-a[i]),那么总共的代价就是，这显然是一个二次函数，那么我们可以对其进行化简，然后直接用公式O（1）得出其最小代价即可，但是这道题目非常毒瘤，对精度要求特别高，所以我们不能通过公式直接求出最小值，我们只能先求出x，然后每一个数每一个数算其代价，这样我们才能ac，下面是这种做法的代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
#define double long double
const int N=1e6+10;
int n;
double a[N],eps=1e-10;
double c[N];
double cal(double d)
{
	double ans=0,b=0;
	for(int i=1;i<=n;i++)
	{
		c[i]=a[i]-(i-1)*d;
		b+=c[i];
	}
	b/=n;
	for(int i=1;i<=n;i++)
		ans+=(c[i]-b)*(c[i]-b);
	return ans;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%Lf",&a[i]);;
		double l=-1e10,r=1e10;
		while(r-l>eps)
		{
			double lmid=l+(r-l)/3.0,rmid=r-(r-l)/3.0;
			if(cal(lmid)>cal(rmid)) l=lmid;
			else r=rmid;
		}
		printf("%.10Lf\n",cal(l));
	}
	return 0;
}

第三种做法：最小二乘法

这是百度上给出的最小二乘法的公式，最小二乘法就是用来最小化误差的平方和寻找数据的最佳函数匹配，利用最小二乘法可以简便地求得未知的函数，并使得这些求得的数据与实际数据之间误差的 平方和最小。

这道题就是用最小二乘法解决的板子题，需要注意的一点就是，由于这道题目对答案精度的要求非常高，所以我们求解b时应该用左边的那个公式而不是右边的那个公式，简单的来说就是能用加就别用乘，乘会加大精度损失，下面是代码：
 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
#define double long double
const int N=1e6+10;
int n;
double a[N];
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		n=read();
		double x=(n+1)/2.0;
		double y=0,t=0,tx=0;
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
			y+=a[i];
			t+=i*a[i];
			tx+=i*i;
		}
		y/=n;
		double k=0;
		for(int i=1;i<=n;i++) k+=(i-x)*(a[i]-y);
		double ttt=0;
		for(int i=1;i<=n;i++) ttt+=(x-i)*(x-i);
		k/=ttt;
		double b=y-k*x;
		double ans=0;
		double tt=k+b;
		for(int i=1;i<=n;i++)
		{
			ans+=(a[i]-tt)*(a[i]-tt);
			tt+=k;
		}
		printf("%.10Lf\n",ans);
	}
	return 0;
}