当前位置：首页 > news >正文

打卡信奥刷题（3443）用C++实现信奥题 P10389 [蓝桥杯 2024 省 A] 成绩统计

news 2026/7/13 8:29:03

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

题目描述

小蓝的班上有nnn个人，一次考试之后小蓝想统计同学们的成绩，第iii名同学的成绩为aia_iai。当小蓝统计完前xxx名同学的成绩后，他可以从1∼x1 \sim x1∼x中选出任意kkk名同学的成绩，计算出这kkk个成绩的方差。小蓝至少要检查多少个人的成
绩，才有可能选出kkk名同学，他们的方差小于一个给定的值TTT？
提示：kkk个数v1,v2,⋯ ,vkv_1, v_2, \cdots , v_kv1,v2,⋯,vk的方差σ2\sigma^2σ2定义为：σ2=∑i=1k(vi−vˉ)2k\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} kσ2=k∑i=1k(vi−vˉ)2，其中vˉ\bar vvˉ表示
viv_ivi的平均值，vˉ=∑i=1kvik\bar v = \dfrac {\sum_{i=1}^k v_i} kvˉ=k∑i=1kvi。

输入格式

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

第二行包含nnn个正整数a1,a2,⋯ ,ana_1, a2, \cdots, a_na1,a2,⋯,an，相邻整数之间使用一个空格分隔。

输出格式

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

输入输出样例 #1

输入 #1

5 3 1 3 2 5 2 3

输出 #1

说明/提示

检查完前三名同学的成绩后，只能选出 $3, 2, 5 $，方差为 $1.56 $；

检查完前四名同学的成绩后，可以选出 $3, 2, 2 $，方差为 $0.22 < 1 $，所以答案为 $4 $。

对于10%10\%10%的评测用例，保证1≤n,k≤1021 ≤ n, k ≤ 10^21≤n,k≤102；
对于30%30\%30%的评测用例，保证1≤n,k≤1031 ≤ n, k ≤ 10^31≤n,k≤103；
对于所有评测用例，保证 $1 ≤ n, k ≤ 10^5 $，$1 ≤ T ≤ 2
^{31} -1 $，$1 ≤ a_i ≤ n $。

C++实现

#include<bits/stdc++.h>#defineinlinline#defineregregister#defineintlonglong#definerep(i,x,y)for(reginti=x;i<=(y);++i)usingnamespacestd;constintN=1e5+5;intn,k,t,a[N],sum_s[N],sum[N],v[N];boolcheck(intx){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];}doubleans=DBL_MAX;rep(i,k,x){doublesum1=sum_s[i]-sum_s[i-k];doublesum2=2*(1.0*sum[i]-sum[i-k])*((1.0*sum[i]-sum[i-k])/k);doublesum3=((1.0*sum[i]-sum[i-k])/k)*((1.0*sum[i]-sum[i-k])/k)*k;ans=min(ans,(sum1-sum2+sum3)/k);}returnans<t;}signedmain(){cin>>n>>k>>t;rep(i,1,n){cin>>a[i];}intl=k,r=n,ans=-1;while(l<=r){intmid=(l+r)>>1;if(check(mid)){r=mid-1;ans=mid;}else{l=mid+1;}}cout<<ans;return0;}