Đề bài:
Thuật toán:
-
Để giải bài toán này, ta giải bài toán trung gian khác như sau
- A là số đoạn nhận X là phần tử trung vị
- B là số đoạn nhận X + 1 là phần tử trung vị
Gọi
=> Result = (A – B) / (n * (n + 1) / 2) ;
Để tính số đoạn nhận X là phần tử trung vị ta chuyển đổi mảng A về, nếu A[i] >= X => A[i] = 1 ngược lại A[i] = 0.
Một đoạn nhận X là trung vị khi và chỉ khi tổng của đoạn đó ko âm. Đến đây, ta dùng cây BIT để tính toán .
Code:
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define long long long const int N = 1e6+10; class FenwickTree { private: long t[N][2]; public: void update(int x, int type) { for (; x <= N; x += x & -x) t[x][type]++; } long get(int x, int type) { long res = 0; for (; x > 0; x -= x & -x) res += t[x][type]; return res; } } BIT; int n, m, k; int a[N], f[N], b[N]; void Enter() { scanf("%d%d", &n, &k); FOR(i, 1, n) scanf("%d", &a[i]); } long calc(int x, int type) { m = 0; for (int i = 1; i <= n; ++i) { f[i] = f[i-1] + (a[i] >= x); b[++m] = 2 * f[i] - i - 1; b[++m] = 2 * f[i-1] - i; } sort(b + 1, b + m + 1); long res = 0; FOR(i, 1, n) { int cur = lower_bound(b + 1, b + m + 1, 2 * f[i - 1] - i) - b; BIT.update(cur, type); cur = lower_bound(b + 1, b + m + 1, 2 * f[i] - i - 1) - b; res += BIT.get(cur, type); } return res; } void Process() { long res = calc(k, 0) - calc(k + 1, 1); double ans = 1ll * n * (n + 1) / 2; ans = res / ans; printf("%.6lf", ans); } int main() { // freopen("input.in", "r", stdin); Enter(); Process(); return 0; } |
BÌNH LUẬN MỚI