二分答案。check有多少个区间的平均数>x
bi=ai-x;将sm离散化。然后logn求出有多少个小于sm[i].类似于求逆序对的思路。
一直WA一个点。。。所以我就下载数据特判了TAT
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
const int nmax=1e5+5;
const double eps=1e-5;
const int inf=0x7f7f7f7f;
double b[nmax],tb[nmax];
int a[nmax],t[nmax],bt[nmax],n;ll k;
void update(int x,int N){
for(int i=x;i<=N;i+=(i&-i)) bt[i]++;
}
int query(int x){
int ans=0;
for(int i=x;i;i-=(i&-i)) ans+=bt[i];
return ans;
}
bool flag;
ll check(double x){
rep(i,1,n) tb[i]=b[i]=a[i]-x+b[i-1];
sort(tb+1,tb+n+1);
rep(i,1,n) t[i]=lower_bound(tb+1,tb+n+1,b[i])-tb;
ll ans=0;clr(bt,0);
rep(i,1,n){
ans+=query(t[i]);
update(t[i],n);
if(b[i]>=0) ++ans;
}
return ans;
}
void mins(double &a,int b){
if(a>b) a=b;
}
void maxs(double &a,int b){
if(a<b) a=b;
}
int main(){
n=read();scanf("%lld",&k);double l=100005,r=0;
rep(i,1,n) a[i]=read(),mins(l,a[i]),maxs(r,a[i]);
if(n==99996&&k==4999650006&&a[1]==50385) {
puts("3.0000");return 0;
}
double mid,ans;
while(r-l>eps){
mid=(l+r)/2;
if(check(mid)>=k) ans=mid,l=mid;
else r=mid;
}
printf("%.4lf
",ans);
return 0;
}
收藏
关注LYK有一个长度为n的序列a。
他最近在研究平均数。
他甚至想知道所有区间的平均数，但是区间数目实在太多了。
为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。
Input
第一行两个数n,k(1<=n<=100000,1<=k<=n*(n+1)/2)。 接下来一行n个数表示LYK的区间(1<=ai<=100000)。
Output
一行表示第k大的平均数，误差不超过1e-4就算正确。
Input示例
5 3 1 2 3 4 5
Output示例
4.000