LYK有一个长度为n的序列a。
他最近在研究平均数。
他甚至想知道所有区间的平均数，但是区间数目实在太多了。
为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。
输入
第一行两个数n,k(1<=n<=100000,1<=k<=n*(n+1)/2)。
接下来一行n个数表示LYK的区间(1<=ai<=100000)。
输出
一行表示第k大的平均数，误差不超过1e-4就算正确。
输入样例
5 3
1 2 3 4 5
输出样例
4.000
首先看题目求区间第k大，首先想到分第k大的平均数x。问题转化为如何快速求任意区间的平均数大于x的个数，先求求前缀和，则可以表示为(sum[r] - sum[l-1])/(r - l +1) > x 的区间个数，转化一下即为sum[r] - r*x > sum[l-1] - (l-1) * x;即形成一个新的数组sum[i]- i * x，求满足条件的区间有多少个，离散化一下，用树状数组统计一下就行。
注意：i从0开始，sum[0] = 0;也要算进去，不然会把0-1的区间漏掉。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; typedef long double ld; typedef long long ll; ll n, k; const ld eps = 1e-6; ld sum[maxn]; ld a[maxn], b[maxn]; ll tmp[maxn]; ll c[maxn]; int lowbit(int x) { return x & (-x); } void add(int x) { for (int i = x; i <= n + 1; i += lowbit(i)) c[i]++; } ll Sum(int x) { ll ans = 0; for (int i = x; i >= 1; i -= lowbit(i)) ans += c[i]; return ans; } ll check(ld mid) { memset(c, 0, sizeof(c)); for (int i = 0; i <= n; i++) { a[i] = b[i] = sum[i] - i * mid; } sort (a, a + n + 1); int m = unique(a, a + n + 1) - a; for (int i = 0; i <= n; i++) { tmp[i] = lower_bound(a, a + m + 1, b[i]) - a + 1; } long long ans = 0; for (int i = 0; i <= n; i++) { ans += Sum(tmp[i]); add(tmp[i]); } return ans; } int main() { int x; scanf("%lld%lld", &n, &k); for (int i = 1; i <= n; i++) { scanf("%d", &x); sum[i] = sum[i - 1] + x; } ld l = 1.0, r = 100000.0; while (r - l >= eps) { ld mid = (l + r) / 2.0; if (check(mid) >= k) { l = mid; } else { r = mid; } } printf("%.4Lf", (r + l) / 2.0); return 0; }
