@zzzc18 2017-09-24T16:54:19.000000Z 字数 1258 阅读 1431

# 2017.09.23 平均数

TEST

## Solution:

#include<cstdio>#include<climits>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int MAXN = 100000+9;int n;LL k;int num[MAXN];double num2[MAXN];double s[MAXN];double tmp[MAXN];LL tot=0;int L,R;void merge_sort(double A2[],int l,int r,double A1[]){    if(l==r)        return;    int mid=(l+r)>>1;    merge_sort(A2,l,mid,A1);    merge_sort(A2,mid+1,r,A1);    int q1=l,q2=mid+1;    int cnt=l;    while(q1<=mid && q2<=r){        if(A1[q1]<A1[q2])            A2[cnt++]=A1[q1++];        else{            A2[cnt++]=A1[q2++];            tot+=mid-q1+1;        }    }    while(q1<=mid) A2[cnt++]=A1[q1++];    while(q2<=r) A2[cnt++]=A1[q2++];    for(int i=l;i<=r;i++) A1[i]=A2[i];}void mergesort(int l,int r,double A[]){    merge_sort(tmp,l,r,A);}void OUT(){    int i;    for(i=1;i<=n;i++)        printf("%.4lf ",s[i]);    puts("");}bool work(double x){    int i;    for(i=1;i<=n;i++) num2[i]=num[i]*1.0-x;    for(i=1;i<=n;i++) s[i]=s[i-1]+num2[i];    tot=0;    mergesort(0,n,s);    //OUT();    //printf("%.4lf %lld\n",x,tot);    return tot>=k;}void solve(){    double l=L*1.0,r=R*1.0;    while(r-l>=0.00001){        double mid=(l+r)/2;        if(work(mid))            r=mid;        else            l=mid;    }    printf("%.4lf\n",l);}int main(){    freopen("ave.in","r",stdin);    freopen("ave.out","w",stdout);    scanf("%d%lld",&n,&k);    int i;    L=INT_MAX;R=INT_MIN;    for(i=1;i<=n;i++){        scanf("%d",&num[i]);        L=min(L,num[i]);        R=max(R,num[i]);    }    solve();    return 0;}

• 私有
• 公开
• 删除