【题解】P10389

P10389（洛谷题面）

题目

题目描述：

小蓝的班上有 $n$ 个人，一次考试之后小蓝想统计同学们的成绩，第 $i$ 名同学的成绩为 $a_i$。当小蓝统计完前 $x$ 名同学的成绩后，他可以从 $1 \sim x$ 中选出任意 $k$ 名同学的成绩，计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成
绩，才有可能选出 $k$ 名同学，他们的方差小于一个给定的值 $T$？
提示：$k$ 个数 $v_1, v_2, \cdots , v_k$ 的方差 $\sigma^2$ 定义为：$\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k$，其中 $\bar v$ 表示
$v_i$ 的平均值，$\bar v = \dfrac {\sum_{i=1}^k v_i} k$。

输入格式：

输入的第一行包含三个正整数 ，相邻整数之间使用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1, a2, \cdots, a_n$ ，相邻整数之间使用一个空格分隔。

输出格式：

输出一行包含一个整数表示答案。如果不能满足条件，输出 $-1$ 。

数据范围与说明：

检查完前三名同学的成绩后，只能选出 ，方差为 ；

检查完前四名同学的成绩后，可以选出 ，方差为 ，所以答案为 。

对于 $10\%$ 的评测用例，保证 $1 ≤ n, k ≤ 10^2$；
对于 $30\%$ 的评测用例，保证 $1 ≤ n, k ≤ 10^3$ ；
对于所有评测用例，保证 ，，。

输入输出样例 #1

输入：

5 3 1
3 2 5 2 3

输出：

4

题意

简述：

小蓝的班上有 $n$ 个人，一次考试之后小蓝想统计同学们的成绩，第 $i$ 名同学的成绩为 $a_i$。当小蓝统计完前 $x$ 名同学的成绩后，他可以从 $1 \sim x$ 中选出任意 $k$ 名同学的成绩，计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成
绩，才有可能选出 $k$ 名同学，他们的方差小于一个给定的值 $T$？
提示：$k$ 个数 $v_1, v_2, \cdots , v_k$ 的方差 $\sigma^2$ 定义为：$\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k$，其中 $\bar v$ 表示
$v_i$ 的平均值，$\bar v = \dfrac {\sum_{i=1}^k v_i} k$。

代码

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
LL n,k,T,a[100005],s[100005],qsum[100005],qpf[100005];
bool check(LL x){
    for(int i=1;i<=x;i++)   s[i]=a[i];
    sort(s+1,s+x+1);
    qsum[0]=0,qpf[0]=0;
    for(int i=1;i<=x;i++)   qsum[i]=qsum[i-1]+s[i];
    for(int i=1;i<=x;i++)   qpf[i]=qpf[i-1]+s[i]*s[i];
    db fc=0,avg=0;
    for(int i=1;i<=k;i++) avg+=(db)s[i]/k;
    fc=(qpf[k]-2*avg*qsum[k]+k*avg*avg)/k;
    if(T>=fc){
        return true;
    }
    for(int i=k+1;i<=x;i++){
        avg=avg-(db)s[i-k]/k+(db)s[i]/k;
        fc=(qpf[i]-qpf[i-k]-2*avg*(qsum[i]-qsum[i-k])+k*avg*avg)/k;
        if(T>=fc){
            return true;
        }
    }
    return false;
}

int main(){
    cin>>n>>k>>T;
    for(int i=1;i<=n;i++)   cin>>a[i];
    LL l=k,r=n;
    LL ans=n+1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if(ans>n) cout<<-1;
    else cout<<ans;
    return 0;
}