51Nod-1711平均数
1512+
题目大意：长度为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)。
程序实现
