参考：http://blog.csdn.net/samjia2000/article/details/51778301
#include<bits/stdc++.h> using namespace std; const double eps=1e-6; const int MAXN=100100; double val[MAXN]; long long a[MAXN]; int n,num[MAXN]; bool cmp(int a,int b) { return val[a]<val[b]; } long long merge(int lef,int rig) { if(lef==rig) return 0; int mid=(lef+rig)>>1; long long ret=0; ret=merge(lef,mid)+merge(mid+1,rig); sort(num+mid+1,num+rig+1); for(int i=lef;i<=mid;i++) ret+=(num+rig+1)-upper_bound(num+mid+1,num+rig+1,num[i]); sort(num+lef,num+rig+1); return ret; } long long cal(double x) { for(int i=1;i<=n;i++) val[i]=a[i]-x*i; sort(num,num+n+1,cmp); return merge(0,n); } int main() { long long k,i; double lef,rig,mid; while(~scanf("%d%lld",&n,&k)) { for(i=1;i<=n;i++) scanf("%lld",&a[i]); for(i=1;i<=n;i++) { a[i]+=a[i-1]; num[i]=i; } num[0]=val[0]=0; lef=0;rig=100000; while(lef+eps<=rig) { mid=(lef+rig)/2; if(cal(mid)>=k) lef=mid; else rig=mid; } printf("%.5f\n",lef); } }