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∑ibj 和
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∑ibj2。根据均值和方差的计算公式：
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\tag1
v=μ(v1,⋯,vn)=n1i=1∑nvi(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)}\tag2
σ2(v1,⋯,vn)=n1i=1∑n(vi−v)2=n1(i=1∑nvi2−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∑nvi2−2vi=1∑nvi+nv2)。这个当然也是 O ( 1 ) O(1) O(1)，但是它的形式更加复杂一点，可以稍微唤醒一下自己学过的数学知识来化简一下。
综上所述，在 O ( n log 2 n ) O(n\log^2n) O(nlog2n) 的时间复杂度内可以完成该题。
AC 代码
#include<iostream>
#include<algorithm>
#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;
}
}