CodeForces 626D Jerry's Protest

时间：2022-04-25 18:01:08

计算前两盘A赢，最后一盘B赢的情况下，B获得的球的值总和大于A获得的球总和值的概率。

存储每一对球的差值有几个，然后处理一下前缀和，暴力枚举就好了......

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#include<vector>

#include<queue>

#include<algorithm>

#include<iostream>

using namespace std;

const int maxn =  + ;

int n;

int a[maxn];

int b[maxn];

int sum[maxn];

int main()

{

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    memset(sum, , sizeof sum);

    memset(b, , sizeof b);

    sort(a+, a + n+);

    for (int i = ; i <= n; i++)

        for (int j = i + ; j <= n; j++)

            b[a[j] - a[i]]++;

    double ans = ;

    for (int i = ; i <= ; i++) sum[i] = sum[i - ] + b[i];

    for (int i = ; i <= ; i++)

        for (int j = ; j <= ; j++)

        {

            if (i + j <= )

                ans = ans + 1.0*b[i] * b[j] * (sum[] - sum[i + j]);

        }

//    printf("%d\n", ans);

    double N = (double)n;

    double f = N*(N - )*N*(N - )*N*(N - ) / 8.0;

    printf("%.6lf\n", 1.0*ans / f);

    return ;

}

相关文章