2022 Niuke multi School Game 2 J. link with arithmetic progress (three points + enumeration)

The question
Give a sequence , The element can be changed to any value , The cost is the square of the difference , Ask the minimum cost of adapting it into an isochronous sequence
Ideas

Suppose the previous sequence is a1,a2,a3……
The modified sequence is b1,b2,b3……
The first item is b1, The tolerance is d
Difference value ci=ai-bi
bi=b1+(i-1)d
The answer is c1c1+c2c2+……=
(a1-(b1+(i-1)d))^2+ (a2-(b1+(i-1)d))^2+……
Then simplify it and find out the tolerance d Take it as an unknown number to get a bivariate primary function
Three points d To narrow it down check When calculating the cost
know d in the future
ci=ai-bi=ai-(b1+(i-1)d)
ci+b1 It's all unknown , Put to one side
ci+b1=ai-(i-1)d=di
c1c1+c2c2+c3c3+……
=(d1-b1)^2+ (d2-b1)^ 2+(d3-b1)^2+……
=nb1b1-2(d1+d2+d3+……)b1+(d1 * d1+d2 * d2+d3 * d3+……)
b1 It's an unknown number
amount to ax^2+by+c Find the extreme value , When x=-b/2a Get extreme value at
b1=(-2(d1+d2+d3+……))/(-2n)=(d1+d2+d3+……)/n
And then calculate ci That's it
ci=di-b1

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e5+10;

long double a[maxn];
long double b[maxn];
long double eps=1e-10;
int n;

long double check(long double d){
    
	long double res=0,sum=0;
	for(int i=1;i<=n;i++){
    
		b[i]=(a[i]-(i-1)*d);
		sum=sum+b[i];
	}
	sum/=n;
	for(int i=1;i<=n;i++){
    
		res=res+(b[i]-sum)*(b[i]-sum);
	}
	return res;
}

int main() {
    
	int _;scanf("%d",&_);
	while(_--){
    
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%Lf",&a[i]);	
		long double l=-1e10,r=1e10;
		while(r-l>eps){
    
			long double mid1=l+(r-l)/3.0,mid2=r-(r-l)/3.0;
			if(check(mid1)>check(mid2)) l=mid1;
			else r=mid2;
			//cout<<_<<" "<<l<<" "<<r<<endl;
		}
		printf("%.10Lf\n",check(l));
	}
	
	return 0;
}