返回题解分享
讨论 / 题解分享/ 帖子详情

成绩统计(编程题) - 题解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
ll n,k,T;
ll a[N],b[N],aa[N],s1[N],s2[N];
bool check(ll n){
    for(int i=1;i<=n;i++)b[i]=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        s1[i]=s1[i-1]+b[i];
        s2[i]=s2[i-1]+b[i]*b[i];
    }
    for(int i=1,e=k;e<=n;e++,i++){
        if(k*(s2[e]-s2[i-1])-(s1[e]-s1[i-1])*(s1[e]-s1[i-1])<k*k*T){
            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,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(r==n&&!check(n))cout<<-1;
    else cout<<l;
    return 0;
}
0 回复 0 转发 0 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!