NKLUCK – spoj

Đề 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
    Gọi

    • 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ị

    => 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;
}
Khuyên dùng

 

Speak Your Mind

*