P10389 [蓝桥杯 2024 省 A] 成绩统计 讲解

· · 题解

大家做题之前应该都会看标签吧（逃

看了标签的都知道，这题要略微运用一点数学知识

思路：

首先想到的思路便是挨个枚举，但是这种思路明显超时（一个绿怎么可能这么简单）。

其次想到的就是前缀和了，但是写着写着会发现问题，那么就要把公式 \sigma^2 = \dfrac {\sum_{i=1}^k\left(v_i-\bar v \right)^2} k 变一变。

发现有两数差的平方，这时就应想到完全平方公式 (a-b)^2=a^2-2ab+b^2 了，拆完后应为：

\sigma^2=\dfrac {\sum_{i=1}^k \left(v_i^2-2v_i\bar v+\bar v^2 \right)} k

可这个式子看起来还是不够可爱，所以继续拆：

\sigma^2=\dfrac {\sum_{i=1}^kv_i^2 - \sum_{i=1}^k2v_i\bar v + k\bar v^2} k

这样就可爱多了，平方和可以用前缀和得出，但是 k 个数的平均值会变，每次都重新处理显然不符合我这种懒癌患者的性子，那该怎么办呢？

回顾一下这句话：其中 \bar v 表示 v_i 的平均值，\bar v = \dfrac {\sum_{i=1}^k v_i} k，平均值不好求，但是 k 个数的和我们可以用前缀和啊，那么式子就变成这样：

\sigma^2=\dfrac {\sum_{i=1}^kv_i^2 - \sum_{i=1}^k2v_i\dfrac {\sum_{i=1}^k v_i} k + k \left( \dfrac {\sum_{i=1}^kv_i} {k}\right)^2} k

得到了这个可爱的式子明明就是一坨，就可以继续往下进行了。

题目让我们求小蓝至少要检查多少个人的成绩，才有可能选出 k 名同学，一个一个判断显然太慢，这时候就需要二分答案了，二分至少要检查多少人。既然要选出 k 名同学，则至少要从 k 个人里选；最多则是 n 名。左右端点就出来了。

接下来就要写 check 函数了，首先我们需要另开一个数组，将原数组里的数据导过来（不能修改原数组，不然会导致后面的处理出现错误）。

既然题里让方差小于 T，那么我们就要使方差尽可能小，要让数据的波动程度尽可能小，所以要将另开的数组排序（不知道为什么的请学习八上数学）。

接下来我们就要用上面的式子求前缀和了，然后找一找最小的方差就行了。

温馨提示：

code:

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i)
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
using namespace std;
const int N=1e5+5;
int n,k,t,a[N],sum_s[N],sum[N],v[N];
bool check(int x){
    rep(i,1,x) v[i]=a[i];
    sort(v+1,v+x+1);
    rep(i,1,x){
        sum_s[i]=sum_s[i-1]+v[i]*v[i];
        sum[i]=sum[i-1]+v[i];
    }
    double ans=DBL_MAX;
    rep(i,k,x){
        double sum1=sum_s[i]-sum_s[i-k];
        double sum2=2*(1.0*sum[i]-sum[i-k])*((1.0*sum[i]-sum[i-k])/k);
        double sum3=((1.0*sum[i]-sum[i-k])/k)*((1.0*sum[i]-sum[i-k])/k)*k;
        ans=min(ans,(sum1-sum2+sum3)/k);
    }   
    return ans<t;
}
signed main(){
    fst;
    cin>>n>>k>>t;
    rep(i,1,n){
        cin>>a[i];
    }
    int l=k,r=n,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}

Link