蓝桥杯 2024 省 A 成绩统计

题目描述

小蓝的班上有 $n$ 个人，一次考试之后小蓝想统计同学们的成绩，第 $i$ 名同学的成绩为 $a_i$ 。当小蓝统计完前 $x$ 名同学的成绩后，他可以从 $1 \sim x$ 中选出任意 $k$ 名同学的成绩，计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成
绩，才有可能选出 $k$ 名同学，他们的方差小于一个给定的值 $T$ ？
提示： $k$ 个数 $v_1, v_2, \cdots , v_k$ 的方差 $\sigma^2$ 定义为： $\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k$ ，其中 $\bar v$ 表示
$v_i$ 的平均值， $\bar v = \dfrac {\sum_{i=1}^k v_i} k$ 。

输入格式

输入的第一行包含三个正整数，相邻整数之间使用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1, a2, \cdots, a_n$ ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。如果不能满足条件，输出 $-1$ 。

样例 #1

样例输入 #1

1 2	5 3 1 3 2 5 2 3

样例输出 #1

提示

检查完前三名同学的成绩后，只能选出，方差为；

检查完前四名同学的成绩后，可以选出，方差为，所以答案为。

对于 $10\%$ 的评测用例，保证 $1 ≤ n, k ≤ 10^2$ ；
对于 $30\%$ 的评测用例，保证 $1 ≤ n, k ≤ 10^3$ ；
对于所有评测用例，保证，，。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
//思路:每次二分答案 对于前mid个数取k个求方差 显然要先排序
//当前k个不满足时就滑动窗口（注意数据类型）
LL n,k,T,a[100005],s[100005],qsum[100005],qpf[100005];
bool check(LL x){
    for(int i=1;i<=x;i++)   s[i]=a[i];
    sort(s+1,s+x+1);//先排序 要使方差更小 那相邻的几个数得接近
    qsum[0]=0,qpf[0]=0;//每次二分都要进来 我们要初始化 防止上一次的值还在
    for(int i=1;i<=x;i++)   qsum[i]=qsum[i-1]+s[i];//前缀和
    for(int i=1;i<=x;i++)   qpf[i]=qpf[i-1]+s[i]*s[i];//前缀平方和
    db fc=0,avg=0;//定义一个双精浮点方差和平均值
    for(int i=1;i<=k;i++) avg+=(db)s[i]/k;//求平均值
    fc=(qpf[k]-2*avg*qsum[k]+k*avg*avg)/k;//方差公式拆分
    //T=Σ(s[i]-avg)^2/k
    //直接平方公式拆分
    if(T>=fc){//先判断前k个
        return true;
    }
    for(int i=k+1;i<=x;i++){
        avg=avg-(db)s[i-k]/k+(db)s[i]/k;//滑动窗口 把尾部的减掉 加当前进来的s[i]
        fc=(qpf[i]-qpf[i-k]-2*avg*(qsum[i]-qsum[i-k])+k*avg*avg)/k;//滑窗判断 每次去尾 加上新进来的数
        if(T>=fc){
            return true;
        }
    }
    return false;
}

int main(){
    cin>>n>>k>>T;
    for(int i=1;i<=n;i++)   cin>>a[i];
    LL l=k,r=n;
    LL ans=n+1;//定义一个比n大的数 没找到曼珠要求的后面直接返回-1
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){//二分答案 找到了就缩小右边看看有没有更小的
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if(ans>n) cout<<-1;
    else cout<<ans;
    return 0;
}