题解 | #获得木头#

本题只需要把 前n项（x-i）^2 a[i] 的公式拆解成xxai-2xiai+iiai 对ai 、2iai 和 iiai分别求前缀合 f1 、 f2和f3 然后把x从1到n遍历一遍取最小的结果 res=min(res,xxf1-f2*x+f3); >

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
#define ll long long
ll f1=0,f2=0,f3=0;
ll n,a[N];

/*
    本题只需要把 前n项（x-i）^2 *a[i] 的公式拆解成x*x*ai-2*x*i*ai+i*i*ai
    对ai 、2*i*ai 和 i*i*ai分别求前缀合 f1 、 f2和f3
    然后把x从1到n遍历一遍取最小的结果
    res=min(res,x*x*f1-f2*x+f3);
*/
int main()
{
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        f1+=a[i];
        f2+=2*i*a[i];
        f3+=i*i*a[i];
    }
    
    ll res= 1e18;
    for(ll i=1;i<=n;i++)
    {
        res=min(res,i*i*f1-i*f2+f3);
    }
    cout<<res<<endl;
    return 0;
}本题只需要把 前n项（x-i）^2 *a[i] 的公式拆解成x*x*ai-2*x*i*ai+i*i*ai
    对ai 、2*i*ai 和 i*i*ai分别求前缀合 f1 、 f2和f3
    然后把x从1到n遍历一遍取最小的结果
    res=min(res,x*x*f1-f2*x+f3);