c++A组成绩统计
作者:
炽热小老弟
,
2024-05-06 19:18:22
,
所有人可见
,
阅读 19
二分+数学(题解整理)
#include<bits/stdc++.h>
using namespace std;
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];
bool check(int mid)
{
for(int i=1;i<=n;i++)
b[i]=a[i];
sort(b+1,b+1+mid);
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++)
{
LL s2=pre2[i+k-1]-pre2[i-1],s=pre[i+k-1]-pre[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;
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))
r=mid;
else l=mid+1;
}
if(check(l)) cout<<l<<endl;
else cout<<-1;
return 0;
}