题解：P10389 [蓝桥杯 2024 省 A] 成绩统计
zhhgdm
·
·
题解
扫一眼题目便知，这是一道我最不擅长的数学题。
仔细观察
\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k
便知道，既然要最小化它，那必然要使 \lvert v_i-\bar v \rvert 尽可能小，也就是让每个数离平均值尽量近，也就是每个数尽量接近。那么对于一个有序数列，要选 k 个数使他们最接近，一定会选 [1,k]、[2,k+1] 这些区间。
然而，我们连数列是什么都不知道，怎么办？二分啊！二分什么呢？二分 x，这样就可以知道数列是谁了。
现在，我们有一种做法，二分 x，再对 1 ∼ x 排序，再遍历区间的结束节点（开始节点也行），再遍历区间，计算方差，判断以所有节点为结束节点的最小方差是否小于 T。
然而 O(nk \log(n)) 的时间复杂度只能那 40 分，我们需要优化。很容易想到前缀和，但是 \bar v 会变，怎么办呢？可以把
\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k
根据完全平方差公式变成
\sigma^2=\dfrac {k\times \bar v+\sum_{i=1}^k v_i^2- \sum_{i=1}^k 2 \times v_i \times \bar v} {k}
$$
\sigma^2=\dfrac {k\times \dfrac {\sum_{i=1}^k v_i} k+\sum_{i=1}^k v_i^2- \sum_{i=1}^k 2 \times v_i \times \dfrac {\sum_{i=1}^k v_i} k} {k}
$$
把 $v_i$ 的前缀和记为 $sum_i$，$v_i^2$ 的前缀和记为 $sum2_i$，那么可以得到方差 $O(1)$ 的计算方法：
$$
\sigma^2=\dfrac {sum_k+sum2_k-2 \times sum_k \times \dfrac {sum_k} k} k
$$
# 完整代码
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
long long a[100005];
long long b[100005];
long long sum[100005];
long long sum2[100005];
long long n,k,T;
bool check(int x){
for(int i=1;i<=x;i++){
b[i]=a[i];
}
sort(b+1,b+x+1);
for(int i=1;i<=x;i++){
sum[i]=sum[i-1]+b[i];
sum2[i]=sum2[i-1]+b[i]*b[i];
}
double ans=1e300;
for(int i=k;i<=x;i++){
ans=min(ans,((sum2[i]-sum2[i-k])+
((1.0*sum[i]-sum[i-k])/k)*((1.0*sum[i]-sum[i-k])/k)*k-
2*(1.0*sum[i]-sum[i-k])*(1.0*sum[i]-sum[i-k])/k)/k);
}
return ans<T;
}
int main(){
cin>>n>>k>>T;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int l=k,r=n,ans=-1;
while(l<=r){
int mid=l+(r-l)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
```
十年 OI 一场空，不开 `long long` 见祖宗。