2017.09.23 平均数

TEST

题目：

Solution:

丧心病狂的出题人连BIT逆续对都要卡
注意由于是对前缀和求逆续对，所以归并排序应该是 $[0,n]$ 的S

#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;
}