19705成绩统计
思路：
-
知识点：
二分答案+前缀和
-
单调性说明：
题目问的是x至少是多少，所以枚举x
当x选定后，任选k名同学，有\(C_x^k\)种选法
=>为了使方差尽可能小，sort之后，选相邻k个最有可能小于\(σ^2\)
=>简化为(x-k+1)种选法
-
当x↑，k不变，sort之后新序列\(σ^2\)↓
当x↓，k不变，sort之后新序列\(σ^2\)↑
(新数加入原排序序列，只会使得k个数取值更密集，比如：2 3 5，加入2之后，2 2 3 5，明显2 2 3方差更小了)
-
单调性+最优解——二分答案
最小的x，向左找
-
check逻辑：
sort(a[1],a[n])
计算前缀和
取数(i∈[k,x])
-
方差计算说明：
代码：
int n,k,l,r,mid;
double t,a[N],tmp[N]={0},prefix1[N]={0},prefix2[N]={0};
bool flag;//tmp用于排序的临时数组 prefix1为ai的前缀和数组 prefix2为(ai)^2的前缀和数组bool check(int x)
{if(x<k) return false;memset(prefix1,0,sizeof(prefix1));//清空memset(prefix2,0,sizeof(prefix2));double sig2=0,avg=0;for(int i=1;i<=x;++i)//赋值-准备排序tmp[i]=a[i];sort(tmp+1,tmp+x+1);//排序for(int i=1;i<=x;++i){//前缀和prefix1[i]=prefix1[i-1]+tmp[i];prefix2[i]=prefix2[i-1]+tmp[i]*tmp[i];}for(int i=k;i<=x;++i){avg=(prefix1[i]-prefix1[i-k])/k;//averagesig2=(prefix2[i]-prefix2[i-k]-k*avg*avg)/k;//sigma^2if(sig2<t) return true;//有一组就行 }return false;
}int main()
{cin>>n>>k>>t;for(int i=1;i<=n;++i)cin>>a[i];l=1,r=n;while(l<r){//向左找 mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}if(check(l)) cout<<l;//最后要检查l是不是答案else cout<<-1;return 0;
}