二分+数学（题解整理）

#include<bits/stdc++.h>
using namespace std;//复杂度Olog^2 (n)  
const int N=100010;
typedef __int128  LL;
int n1,k1,t1,a1[N];
LL n,k,t,a[N],b[N],pre[N],pre2[N];//b是临时使用数组 
bool check(int mid)
{
    //int b[N];
    for(int i=1;i<=n;i++)
    b[i]=a[i];
    sort(b+1,b+1+mid);//排序 然后处理前缀和  和平方的前缀和  这里mid是细节 第一次写成n了 
    for(int i=1;i<=n;i++)
    pre[i]=pre[i-1]+b[i],pre2[i]=pre2[i-1]+b[i]*b[i];
    for(int i=1;i+k-1<=mid;i++)//i+k-1 是k这个区间的右端点
    {
        LL s2=pre2[i+k-1]-pre2[i-1],s=pre[i+k-1]-pre[i-1];//这里前缀和的细节 要包含i这个点的值要减i-1 
        if(k*s2-s*s<k*k*t)
        return true;
     } 
     return false;
}

int main()
{
    cin>>n1>>k1>>t1;
    n=n1,k=k1,t=t1;//t很大的 剩下1e5 
    for(int i=1;i<n;i++)
    cin>>a1[i],a[i]=a1[i];

    int l=1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))//大区间可以的话小点试试？ 找到能通过check的最小的区间
        r=mid;
        else l=mid+1;
    }
    if(check(l)) cout<<l<<endl;
    //else if(check(r)) cout<<r<<endl;
    else cout<<-1;
    return 0; 
 }