当前位置: 代码迷 >> 综合 >> 51Nod 1711 平均数
  详细解决方案

51Nod 1711 平均数

热度:57   发布时间:2023-12-01 21:23:56.0

题目传送门
代码:

#include<bits/stdc++.h>
using namespace std;#define MEM(a,b,start,end) for(int ii=start;ii<=end;ii++) a[ii]=b
#define low(x) (x&(-x))
typedef long long LL;
typedef double D;
const int maxn=100000+100;
const double EPS=1e-6;int tree[maxn];
D ans[maxn];
struct Node{D val;int id;
}node[maxn];
int n;
LL k;inline bool cmp(Node a,Node b){return a.val<b.val;
}inline void add(int ind,int val){while(ind<=n+1){tree[ind]+=val;ind+=low(ind);}
}inline LL sum(int ind){LL s=0;while(ind){s+=tree[ind];ind-=low(ind);}return s;
}bool kaven(double x){MEM(tree,0,1,n+1);LL cnt=0;for(int i=0;i<=n;i++) node[i].val=ans[i]-x*i,node[i].id=i+1;sort(node,node+1+n,cmp);for(int i=0;i<=n;i++){cnt+=sum(node[i].id);add(node[i].id,1);}if(cnt>=k) return true;return false;
}int main(){scanf("%d%lld",&n,&k);ans[0]=0.0;for(int i=1;i<=n;i++) scanf("%lf",&ans[i]),ans[i]+=ans[i-1];D l=0,r=100000.0;while(r-l>=EPS){D mid=(l+r)/2.0;if(kaven(mid)) l=mid;else  r=mid;}printf("%.5f\n",(l+r)/2.0);
}