基准时间限制：4 秒 空间限制：131072 KB 分值: 80

他最近在研究平均数。

他甚至想知道所有区间的平均数，但是区间数目实在太多了。

为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。

 

 

第一行两个数n,k(1<=n<=100000,1<=k<=n*(n+1)/2)。

接下来一行n个数表示LYK的区间(1<=ai<=100000)。

 

 

一行表示第k大的平均数，误差不超过1e-4就算正确。

Input示例

5 3

1 2 3 4 5

Output示例

4.000

题意：

思路：

二分答案,假设平均数为t,那么(sum[i]-sum[j])/(i-j)>=t;变形得sum[i]-t*i>=sum[j]-t*j(0<=j<i);
temp[i]=sum[i]-t*i;
即对于每个temp[i]统计有多少个temp[j]<=temp[i],每个i的和再和k比较就可以对t的取值进行二分了;

AC代码：

#include <bits/stdc++.h>

/*

#include <iostream>

#include <queue>

#include <cmath>

#include <map>

#include <cstring>

#include <algorithm>

#include <cstdio>

*/

using namespace std;

#define Riep(n) for(int i=1;i<=n;i++)

#define Riop(n) for(int i=0;i<n;i++)

#define Rjep(n) for(int j=1;j<=n;j++)

#define Rjop(n) for(int j=0;j<n;j++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef long long LL;

const LL mod=1e9+;

const double PI=acos(-1.0);

const LL inf=1e18;

const int N=1e5+;

int n,num[N];

LL k;

double sum[N],a[N],temp[N];

int lowbit(int x)

{

    return x&(-x);

}

void update(int x)

{

    while(x<=n)

    {

        num[x]++;

        x+=lowbit(x);

    }

}

int query(int x)

{

    int ans=;

    while(x>)

    {

        ans+=num[x];

        x-=lowbit(x);

    }

    return ans;

}

struct node

{

    double temp;

    int id,pos;

}po[N];

int cmp1(node x,node y)

{

    if(x.temp==y.temp)x.id<y.id;

    return x.temp<y.temp;

}

int cmp2(node x,node y)

{

    return x.id<y.id;

}

int check(double x)

{

    mst(num,);

    LL ans=;

    for(int i=;i<=n;i++)

    {

        po[i].temp=sum[i]-x*i;

        po[i].id=i;

    }

    sort(po+,po+n+,cmp1);

    for(int i=;i<=n;i++)po[i].pos=i;//离散化

    sort(po+,po+n+,cmp2);

    for(int i=;i<=n;i++)

    {

        if(po[i].temp>=)ans++;//还有0的情况;

        ans=ans+(LL)query(po[i].pos);

        update(po[i].pos);

    }

    if(ans>=k)return ;

    return ;

}

int main()

{

      cin>>n>>k;

      Riep(n)

      {

          scanf("%lf",&a[i]);

          sum[i]=sum[i-]+a[i];

      }

      double l=,r=;

      while(abs(r-l)>=0.0001)

      {

          double mid=(l+r)/;

          if(check(mid))l=mid;

          else r=mid;

      }

      printf("%.8lf\n",l);

    return ;

}