【 问题描述】
有一天， 小 A 得到了一个长度为 n 的序列。
他把这个序列的所有连续子序列都列了出来， 并对每一个子序列
都求了其平均值， 然后他把这些平均值写在纸上， 并对它们进行排序，
最后他报出了第 k 小的平均值。
你要做的就是模仿他的过程。
【 输入格式】
第一行两个整数 n,k， 意义如题中所述。
第二行 n 个正整数， 即为小 A 得到的序列。
【 输出格式】
一行一个实数， 表示第 k 小的平均值， 保留到小数点后 4 位。
【 样例输入输出】
| ave.in | ave.out |
| 6 10 3 5 4 6 1 2 |
3.6667 |
【 数据范围与约定】
对于 40%的数据， n≤1000
对于 100%的数据， n≤100000， k≤n*(n+1)/2， 序列中的数≤109
/* 第 k 大不易直接求， 我们想到二分， 则原问题转变为求区间平均 值小于 x 的区间数量。 考虑把序列中的每个数减去 x， 则我们只需求 区间和小于 0 的区间数量。 我们对这个序列求前缀和， 则区间[l,r]和 小于 0 当且仅当 Sl-1> Sr ， 答案即为前缀和序列 S 的逆序对数量， 使 用经典的归并排序即可解决， 时间复杂度 O(nlog2n)。 */ #include <cstdio> #include <iostream> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <queue> using namespace std; typedef double db; typedef long long ll; const int N=100010; const db eps=1e-6; db b[N],c[N]; int a[N]; ll ans=0; int n; void solve(int l,int r){ if(l==r) return; int M=l+r>>1; solve(l,M);solve(M+1,r); int i=l,j=M+1,k=l-1; while(i<=M&&j<=r){ if(b[i]<b[j]) c[++k]=b[i++]; else c[++k]=b[j++],ans+=M-i+1; } while(i<=M) c[++k]=b[i++]; while(j<=r) c[++k]=b[j++]; for(i=l;i<=r;i++) b[i]=c[i]; } ll calc(db x){ b[0]=0; for(int i=1;i<=n;i++) b[i]=a[i]-x+b[i-1]; ans=0; solve(0,n); return ans; } int main(){ freopen("ave.in","r",stdin); freopen("ave.out","w",stdout); int mx=0,i; db lb,rb,mid; ll x; scanf("%d %lld",&n,&x); for(i=1;i<=n;i++) scanf("%d",&a[i]),mx=max(mx,a[i]); lb=0;rb=mx; while(rb-lb>eps){ mid=(lb+rb)/2; if(calc(mid)<x) lb=mid; else rb=mid; } printf("%.4lf ",lb); return 0; }