题解

算法分析

当和固定的时候，段数越多，越平均则平方和越小。 $s_i$表示$1...i$的前缀和

我们需要找到某段的$s_i-s_j$>=$s_j-s_k$,也就是等于找到$s_i$ >= $2 \times s_j -s_k$的最小的$j$,同时我们可以根据直觉去判断最后一段和一定是越小越好，这样符合要求的段数才越多。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long LL;
LL w[N],q[N],g[N],s[N]; //g[j]表示所有以j结尾的方案中，对应的倒数第二段的结尾
LL get(int k) //得到
{
    return 2*s[k]-s[g[k]];
}
int main()
{
    int n,type;
    cin>>n>>type;
    for(int i=1;i<=n;i++) //获取数据
    {
        cin>>w[i];
    }
    for(int i=1;i<=n;i++) //前缀和
    {
        s[i]=s[i-1]+w[i];
    }
    int hh=0,tt=0; //单调队列
    for(int i=1;i<=n;i++)
    {
        while(hh<=tt&&s[i]>=get(q[hh])) hh++; //当前队头符合要求，继续看下个位置
        hh--; //回到符合的位置
        g[i]=q[hh]; //记录位置
        while(hh<=tt&&get(i)<=get(q[tt])) tt--; //删除前面的比当前元素大的数
        q[++tt]=i; //加入单调队列之中
    }
    LL res=0;
    for(int i=n;i;i=g[i]) //一段一段往前推
    {
        LL sum=s[i]-s[g[i]];
        res+=sum*sum;
    }
    cout<<res;
    return 0;
}