二分学习·P10389 [蓝桥杯 2024 省 A] 成绩统计

P10389 成绩统计

当时在考场上完全没有头绪，想暴力枚举，结果都不知道怎么写，果然还是有妙法在其中。

  题目的描述如下（省流不了）：
  小蓝的班上有

n

n

n 个人，一次考试之后小蓝想统计同学们的成绩，第

i

i

i 名同学的成绩为

a

i

a_i

ai​。当小蓝统计完前

x

x

x 名同学的成绩后，他可以从

1

∼

x

1 \sim x

1∼x 中选出任意

k

k

k 名同学的成绩，计算出这

k

k

k 个成绩的方差。小蓝至少要检查多少个人的成绩，才有可能选出

k

k

k 名同学，他们的方差小于一个给定的值

T

T

T？

分析

  参考了一些大佬的思路，这题最好的方法就是二分，它符合二分的条件——如果能在第

1

1

1 到第

x

x

x 名中找到想要的这

k

k

k 个同学，那么在第

1

1

1 到

y

(

y

>

x

)

y(y>x)

y(y>x) 名中也能找到这

k

k

k 个同学。考虑对

x

x

x 进行二分，初始区间是

[

l

,

r

]

=

[

k

,

n

]

[l,r]=[k,n]

[l,r]=[k,n]，如果

x

=

⌊

(

l

+

r

)

/

2

⌋

x=\lfloor(l+r)/2\rfloor

x=⌊(l+r)/2⌋ 不符合要求，那么就在

[

x

,

r

]

[x,r]

[x,r] 中寻找

x

x

x；否则在

[

l

,

x

]

[l,x]

[l,x] 中寻找

x

x

x。对

x

x

x 的寻找需要耗费

O

(

log

⁡

(

n

−

k

)

)

O(\log (n-k))

O(log(n−k)) 的时间。
  对于固定的

x

x

x，要判断第

1

1

1 到

x

x

x 名同学的成绩是否符合条件，可以先对这

x

x

x 名同学的成绩排序（升序、降序均可，复杂度

O

(

x

log

⁡

x

)

O(x\log x)

O(xlogx)）。方差最小时，一定是连续的

k

k

k 名同学，这个是可以理论证明的。 因而只需要暴力枚举所有的连续的

k

k

k 个同学，这一共会有

x

−

k

+

1

x-k+1

x−k+1 种情况需要枚举。
  对于每一个枚举，我们都能用

O

(

1

)

O(1)

O(1) 的时间来判断。实现这个复杂度的前提是，在进行排序后，用两个前缀和数组分别维护前

i

i

i 位同学的成绩和、成绩平方之和。不妨记他们的成绩是

b

1

∼

b

x

b_1\sim b_x

b1​∼bx​，也就是需要维护

p

r

e

[

i

]

=

∑

j

=

1

i

b

j

\mathit{pre}[i]=\displaystyle\sum_{j=1}^i b_j

pre[i]=j=1∑i​bj​ 和

s

q

_

p

r

e

[

i

]

=

∑

j

=

1

i

b

j

2

\mathit{sq\_pre}[i]=\displaystyle\sum_{j=1}^ib_j^2

sq_pre[i]=j=1∑i​bj2​。根据均值和方差的计算公式：

v

‾

=

μ

(

v

1

,

⋯
 

,

v

n

)

=

1

n

∑

i

=

1

n

v

i

(1)

\overline v=\mu(v_1,\cdots,v_n)=\cfrac{1}{n}\sum_{i=1}^nv_i ag1

v=μ(v1​,⋯,vn​)=n1​i=1∑n​vi​(1)

σ

2

(

v

1

,

⋯
 

,

v

n

)

=

1

n

∑

i

=

1

n

(

v

i

−

v

‾

)

2

=

1

n

(

∑

i

=

1

n

v

i

2

−

n

v

‾

2

)

(2)

\sigma^2(v_1,\cdots,v_n)=\cfrac{1}{n}\sum_{i=1}^n(v_i-\overline v)^2= {\cfrac{1}{n}\left(\sum_{i=1}^nv_i^2-n\overline v^2\right)} ag2

σ2(v1​,⋯,vn​)=n1​i=1∑n​(vi​−v)2=n1​(i=1∑n​vi2​−nv2)(2)

  两者都能在

O

(

1

)

O(1)

O(1) 的复杂度内计算得出。

我目前看到的两篇题解都写成了

σ

2

=

1

n

(

∑

i

=

1

n

v

i

2

−

2

v

‾

∑

i

=

1

n

v

i

+

n

v

‾

2

)

\sigma^2=\displaystyle\cfrac{1}{n}\left(\sum_{i=1}^nv_i^2-2\overline v\sum_{i=1}^nv_i+n\overline v^2\right)

σ2=n1​(i=1∑n​vi2​−2vi=1∑n​vi​+nv2)。这个当然也是

O

(

1

)

O(1)

O(1)，但是它的形式更加复杂一点，可以稍微唤醒一下自己学过的数学知识来化简一下。

  综上所述，在

O

(

n

log

⁡

2

n

)

O(n\log^2n)

O(nlog2n) 的时间复杂度内可以完成该题。

AC 代码

#include
#include
#define N 100005
using namespace std;
int n,k,t,a[N]; 
double num[N],sq_pre[N],pre[N];
bool cmp(double x,double y){return x<y;}
bool testOK(int x){
for(int i=1;i<=x;i++)
num[i]=a[i];
sort(num+1,num+x+1,cmp);
for(int i=1;i<=x;i++){
pre[i]=pre[i-1]+num[i];
sq_pre[i]=sq_pre[i-1]+num[i]*num[i];
}
for(int begin=1;begin+k-1<=x;begin++)
if(sq_pre[begin+k-1]-sq_pre[begin-1]-(pre[begin+k-1]-pre[begin-1])*(pre[begin+k-1]-pre[begin-1])/k<k*(double)t)
return true;
return false;
}
int main(){
cin>>n>>k>>t;
if(k>n)
return printf("-1"),0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int left=k,right=n,mid;
while(true){
if(left==right)
return printf("%d",testOK(left)?left:-1),0;
else if(left+1==right){
if(testOK(left))
printf("%d",left);
else if(testOK(right))
printf("%d",right);
else
printf("-1");
return 0;
}
mid=(left+right)/2;
if(testOK(mid))
right=mid;
else
left=mid;
}
}