D.探索的时光

数学规律

f(i)=(x-i)^2*a[i]

=(xx+ii-2xi)*a[i]

=xxa[i]-2xia[i]+ii*a[i]

（数学符号不会打，用S f()表示i为从1到n的f()的值的和其实就是∑）

s f(i)=xx(s a[i])-x*(s 2ia[i])+(s iia[i] )

可以发现除了x都是常量

预处理出常量然后遍历x的值取min就可以了

#include<iostream>
using namespace std;
typedef long long int ll;
const int N=1e5+10;
int n;
ll a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    ll x=0,y=0,z=0;
    for(ll i=1;i<=n;++i){
        x+=a[i];
        y+=2*i*a[i];
        z+=i*i*a[i];
    }
    ll ans=0x3f3f3f3f3f3f3f3f;
    for(ll i=1;i<=n;++i){
        ans=min(ans,i*i*x-i*y+z);
    }
    cout<<ans<<endl;
}