当前位置:首页 > 二分 > 正文
51Nod-1711平均数
993+

题目大意:长度为n的数组a,有n*(n+1)/2个区间,平均值第k大的区间的平均值是多少?

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就算正确。

Sample Input

5 3
1 2 3 4 5

Sample Output

4.000

解题思路

二分平均值,然后将所有数据减去平均值,统计有多少个大于等于平均值的区间,如果超过k个,平均值太小了,猜大一点;否则平均值太大了,猜小一点。

右端点减去左端点,区间和不小于零即可,暴力枚举超时,可以用树状数组优化:从小到大添加前缀和端点,对于右端点j,需要找一个前缀和小的左端点,即he(j-1)。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

51Nod-1711平均数:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!