题意
给一个序列，对于其中的元素可以改变为任意值，花费为差值的平方，问将其改编为等差序列的最小花费
思路
假设之前的序列为a1,a2,a3……
修改后的序列为b1,b2,b3……
首项为b1，公差为d
差值ci=ai-bi
bi=b1+(i-1)d
答案就是c1c1+c2c2+……=
(a1-(b1+(i-1)d))^2+ (a2-(b1+(i-1)d))^2+……
然后化简出来发现把公差d当作未知数得到二元一次函数
三分d来缩小范围 check的时候计算代价
知道d以后
ci=ai-bi=ai-(b1+(i-1)d)
ci+b1都是未知的，放到一侧
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是未知数
相当于ax^2+by+c求极值，当x=-b/2a时取得极值
b1=(-2(d1+d2+d3+……))/(-2n)=(d1+d2+d3+……)/n
然后在计算ci就行了
ci=di-b1
代码
#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; }
