CodeForces 626D Jerry's Protest

Posted on By 二价氢

题目大意

给定\(n^2\)个小于5000的数,现在从里面任取3个数(可重复)组成有序三元组\((a,b,c)\),求\(a + b < c\)的概率。

做法

首先,大意已经进行了简化,不过保留了原题的难点,考虑到每个数都很小,所以我们可以用统排求出取得每个数的概率,然后可以枚举\(a, b\),求出\(c > a + b\)的概率。复杂度\(O(n^2 + a^2)\)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 5, maxc = 2000 * 2000 + 5;
int a[maxn], n;
long long rn[maxn * 2 + 1], prn[maxn * 2 + 1];
long long ans = 0;
double r = 0;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(&a[0], &a[n]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            rn[a[i] - a[j]]++;
    for (int i = 1; i <= maxn * 2; i++)
        prn[i] = prn[i - 1] + rn[i];
    r = prn[maxn * 2] * prn[maxn * 2] * prn[maxn * 2];
    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < maxn; j++)
            ans += (prn[maxn * 2] - prn[i + j]) * rn[i] * rn[j];
    printf("%.10f\n", ans / r);
    return 0;
}