题目描述
给你两个长度为 \(n\) 的序列 \(a\) 和 \(b\)，让你选 \(n\) 个 \(c_i \in [a_i,b_i]\)，使得 \(\frac{1}{n} \sum_{i=1}^n (c_i- \overline c)^2\) 最大。
具体思路
首先我们从方差的定义出发，方差代表了数据的波动程度，公式为：$$s^2=\frac{1}{n} \sum_{i=1}^n (a_i- \overline a)^2$$
其中， \(\overline a =\frac{1}{n} \sum_{i=1}^n a_i\)，\(s\) 为方差。
那么我们要让波动程度最大，那就直接选区间的两个端点，但是我们肯定不能直接去枚举选每个区间选左端点还是右端点。
通过思考发现，前一部分我们选左端点，后面部分选右端点，可以导致波动程度最大。但是我们不知道断点应该设在哪里，所以通过枚举断点即可。
那我们显然不可能每次都求一次和，于是考虑化式子然后前缀和解决。
\[s^2=\frac{1}{n}(\sum_{i=1}^n a_i^2+n \times (\frac{\sum_{i=1}^n a_i}{n})^2-2 \times \frac{\sum_{i=1}^n a_i}{n} \times \sum_{i=1}^n a_i)
\]
\[s^2=\frac{1}{n}(\sum_{i=1}^n a_i^2+\frac{(\sum_{i=1}^n a_i)^2}{n}-2 \times \frac{(\sum_{i=1}^n a_i)^2}{n})
\]
\[s^2=\frac{1}{n}(\sum_{i=1}^n a_i^2-\frac{(\sum_{i=1}^n a_i)^2}{n})
\]
\[s^2 \times n^2=n \times (\sum_{i=1}^n a_i^2-\frac{(\sum_{i=1}^n a_i)^2}{n})
\]
\[s^2 \times n^2=n \times \sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2
\]
由于我们求的是 \(a\) 的前一段和 \(b\) 的后一段的信息和，因此需要预处理 \(a\) 的前缀和，\(b\) 的后缀和，\(a\) 的前缀平方和，\(b\) 的后缀平方和。
Code
#include<bits/stdc++.h>
using namespace std;
typedef __int128 LL;
inline void write(LL x){
static int sta[35];int top=0;
do{sta[++top]=x%10;x/=10;}while(x);
while(top)putchar(sta[top--]+'0');
}
const int N=1e6+5;
int a[N],b[N];
LL sa1[N],sa2[N],sb1[N],sb2[N];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
sa1[i]=sa1[i-1]+a[i];
sa2[i]=sa2[i-1]+(LL)a[i]*a[i];
}
for(int i=n;i>=1;i--){
sb1[i]=sb1[i+1]+b[i];
sb2[i]=sb2[i+1]+(LL)b[i]*b[i];
}
LL ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,n*(sa2[i]+sb2[i+1])-(sa1[i]+sb1[i+1])*(sa1[i]+sb1[i+1]));
}
write(ans);
return 0;
}