探索的时光

D探索的时光

//这是个数学问题
//整理f(i)=(x-i)^2*a[i]这个式子
//得到f(i)=(x^2+i^2-2*x*i)*a[i]
//再求和得到sum=x*x*(a1+a2+...+an)+1^2*a1+2^2*a2+...+n^2*an-2*x*(1*a1+2*a2+...+n*an)
//然后利用高中的数学知识（一元二次方程）求解
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll a[100005];
void solve(){
    ll n;
    ll ans=1e18+9,sum=0,sum1=0,sum2=0;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        sum1+=i*a[i];
        sum2+=i*i*a[i];
    }
    ll x;
    double gg=sum1*1.0/sum;
    if(gg>=1&&gg<=n){
        ll xx=ceil(sum1*1.0/sum);
        ll yy=floor(sum1*1.0/sum);
        if(xx>=1&&xx<=n){
            
        x=xx;
        ans=min(ans,x*x*sum+sum2-2*x*sum1);
        }
        if(yy>=1&&yy<=n){x=yy;
        ans=min(ans,x*x*sum+sum2-2*x*sum1);
                        }
    }else if(gg>n){
        x=n;
        ans=x*x*sum+sum2-2*x*sum1;
    }else{
        x=1;
        ans=x*x*sum+sum2-2*x*sum1;
    }
    cout<<ans;
	return ;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _;
	//cin>>_;
	_=1;
	while(_--){
		solve();
	}
	return 0;
}