[2022 Niuke Game 2 J question link with arithmetic progress] three part set three part / three part extreme value / linear equation fitting least square method

Topic link

Topic

The question ：

Give you a length of n Sequence a, For each element , You can change it to any value , But the cost is the square of their difference , What is the minimum cost of changing this sequence into an arithmetic sequence

analysis ：

In fact, if you look at this minimum value problem, it is easy to think of three points , Because the curve of his function is quadratic , There is an extreme value , So we can use quadratic function to do , It's equal difference of three points d, Then look at the left third d Value represents the minimum cost and the right third of the minimum cost to compare , This is a common idea of three points , Then in the judgment function of three points , Is the curve of a quadratic function , Just find the best value , But this precision card is particularly dead , You can't multiply it directly , Add it up slowly , This is also a skill , Then take a look at the code of the extreme value of three points ：

#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];
namespace GTI
{
    
    char gc(void)
       {
    
        const int S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t) t = buf + fread(s = buf, 1, S, stdin);
        if (s == t) return EOF;
        return *s++;
    }
    int read(void)
       {
    
        int a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc()) b ^= (c == '-');
        for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
        return b ? a : -a;
    }
}
using GTI::read;
double cal(double d)
{
    
	double ans=0,b=0;
	for(int i=1;i<=n;i++)
	{
    
		b += a[i]-(i-1)*d;
	}
	b /= n;
	for(int i=1;i<=n;i++){
    
		double t = a[i]-(i-1)*d;
		ans += (t-b)*(t-b);
	}
	return ans;
}
int main()
{
    
	int T;
	cin>>T;
	while(T--)
	{
    
		n=read();
		for(int i=1;i<=n;i++) a[i]=read();
		double l=-1e9,r=1e9;
		while(fabs(r-l)>eps)
		{
    
			double lmid=l+(r-l)/3,rmid=r-(r-l)/3;
			if(cal(lmid)>cal(rmid)) l=lmid;
			else r=rmid;
		}
		printf("%.10Lf\n",cal(l));
	}
	return 0;
}

Least square method

The arithmetic sequence can be regarded as a straight line , Then it is equivalent to linear fitting , Just move the least square method you learned in high school , But pay attention to the formula with less multiplication , Then the loss of accuracy will be small , Now look at the code ：

 
#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;
}