自动搬运

查看原文

来自洛谷，原作者为

	xy_mc 代词使用牠| stay hungry,stay foolish.

搬运于2025-08-24 22:57:30，当前版本为作者最后更新于2025-01-25 21:02:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

大家做题之前应该都会看标签吧（逃

看了标签的都知道，这题要略微运用一点数学知识

思路：

首先想到的思路便是挨个枚举，但是这种思路明显超时（一个绿怎么可能这么简单）。

其次想到的就是前缀和了，但是写着写着会发现问题，那么就要把公式 $ \sigma^2 = \dfrac {\sum_{i=1}^k\left(v_i-\bar v \right)^2} k$ 变一变。

发现有两数差的平方，这时就应想到完全平方公式 $(a-b)^2=a^2-2ab+b^2$ 了，拆完后应为：

$$\sigma^2=\dfrac {\sum_{i=1}^k \left(v_i^2-2v_i\bar v+\bar v^2 \right)} k $$

可这个式子看起来还是不够可爱，所以继续拆：

$$\sigma^2=\dfrac {\sum_{i=1}^kv_i^2 - \sum_{i=1}^k2v_i\bar v + k\bar v^2} k $$

这样就可爱多了，平方和可以用前缀和得出，但是 $k$ 个数的平均值会变，每次都重新处理显然不符合我这种懒癌患者的性子，那该怎么办呢？

回顾一下这句话：其中 $\bar v$ 表示 $v_i$ 的平均值，$\bar v = \dfrac {\sum_{i=1}^k v_i} k$，平均值不好求，但是 $k$ 个数的和我们可以用前缀和啊，那么式子就变成这样：

$$\sigma^2=\dfrac {\sum_{i=1}^kv_i^2 - \sum_{i=1}^k2v_i\dfrac {\sum_{i=1}^k v_i} k + k \left( \dfrac {\sum_{i=1}^kv_i} {k}\right)^2} k $$

得到了这个可爱的式子明明就是一坨，就可以继续往下进行了。

---

题目让我们求小蓝至少要检查多少个人的成绩，才有可能选出 $k$ 名同学，一个一个判断显然太慢，这时候就需要二分答案了，二分至少要检查多少人。既然要选出 $k$ 名同学，则至少要从 $k$ 个人里选；最多则是 $n$ 名。左右端点就出来了。

---

接下来就要写 check 函数了，首先我们需要另开一个数组，将原数组里的数据导过来（不能修改原数组，不然会导致后面的处理出现错误）。

既然题里让方差小于 $T$，那么我们就要使方差尽可能小，要让数据的波动程度尽可能小，所以要将另开的数组排序（不知道为什么的请学习八上数学）。

接下来我们就要用上面的式子求前缀和了，然后找一找最小的方差就行了。

温馨提示：

• 求区间和时，千万不要 $-1$，不然会使元素个数多出来一个，就错了（本蒟蒻在这上面卡了好久）。

code:

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i)
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
using namespace std;
const int N=1e5+5;
int n,k,t,a[N],sum_s[N],sum[N],v[N];
bool check(int x){
	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];
	}
	double ans=DBL_MAX;
	rep(i,k,x){
		double sum1=sum_s[i]-sum_s[i-k];
		double sum2=2*(1.0*sum[i]-sum[i-k])*((1.0*sum[i]-sum[i-k])/k);
		double sum3=((1.0*sum[i]-sum[i-k])/k)*((1.0*sum[i]-sum[i-k])/k)*k;
		ans=min(ans,(sum1-sum2+sum3)/k);
	}	
	return ans<t;
}
signed main(){
	fst;
	cin>>n>>k>>t;
	rep(i,1,n){
		cin>>a[i];
	}
	int l=k,r=n,ans=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<ans;
	return 0;
}

Link