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

P10389 成绩统计

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

  题目的描述如下（省流不了）：
  小蓝的班上有 $n$ 个人，一次考试之后小蓝想统计同学们的成绩，第 $i$ 名同学的成绩为 $a_i$。当小蓝统计完前 $x$ 名同学的成绩后，他可以从 $1\sim x$ 中选出任意 $k$ 名同学的成绩，计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成绩，才有可能选出 $k$ 名同学，他们的方差小于一个给定的值 $T$？

分析

  参考了一些大佬的思路，这题最好的方法就是二分，它符合二分的条件——如果能在第 $1$ 到第 $x$ 名中找到想要的这 $k$ 个同学，那么在第 $1$ 到 $y(y>x)$ 名中也能找到这 $k$ 个同学。考虑对 $x$ 进行二分，初始区间是 $[l,r]=[k,n]$，如果 $x=\lfloor (l+r)/2\rfloor$ 不符合要求，那么就在 $[x,r]$ 中寻找 $x$；否则在 $[l,x]$ 中寻找 $x$。对 $x$ 的寻找需要耗费 $O(\log (n-k))$ 的时间。
  对于固定的 $x$，要判断第 $1$ 到 $x$ 名同学的成绩是否符合条件，可以先对这 $x$ 名同学的成绩排序（升序、降序均可，复杂度 $O(x\log x)$）。方差最小时，一定是连续的 $k$ 名同学，这个是可以理论证明的。 因而只需要暴力枚举所有的连续的 $k$ 个同学，这一共会有 $x-k+1$ 种情况需要枚举。
  对于每一个枚举，我们都能用 $O(1)$ 的时间来判断。实现这个复杂度的前提是，在进行排序后，用两个前缀和数组分别维护前 $i$ 位同学的成绩和、成绩平方之和。不妨记他们的成绩是 $b_1\sim b_x$，也就是需要维护 $pre[i]=\sum _{j=1}^i{b}_j$ 和 $sq\_pre[i]=\sum _{j=1}^i{b}_j^2$。根据均值和方差的计算公式：
$$\overline{v}=\mu (v_1,\cdots ,v_n)=\frac{1}{n}\sum _{i=1}^n{v}_i\text{\hspace{1em}(1)}$$$${\sigma }^2(v_1,\cdots ,v_n)=\frac{1}{n}\sum _{i=1}^n(v_i-\overline{v}{)}^2=\frac{1}{n}\left(\sum _{i=1}^n{v}_i^2-n{\overline{v}}^2\right)\text{\hspace{1em}(2)}$$

  两者都能在 $O(1)$ 的复杂度内计算得出。

我目前看到的两篇题解都写成了 ${\sigma }^2=\frac{1}{n}\left(\sum _{i=1}^n{v}_i^2-2\overline{v}\sum _{i=1}^n{v}_i+n{\overline{v}}^2\right)$。这个当然也是 $O(1)$，但是它的形式更加复杂一点，可以稍微唤醒一下自己学过的数学知识来化简一下。

  综上所述，在 $O(n{\log }^{2}n)$ 的时间复杂度内可以完成该题。

AC 代码

#include<iostream>
#include<algorithm>
#define N 100005using 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);elseprintf("-1");return 0;}mid=(left+right)/2;if(testOK(mid))right=mid;elseleft=mid;}
}