题解：CF626D Jerry's Protest
a_small_penguin
·
·
题解
什么是 DP？布吉岛……
于是我用前缀和淼过去了。
首先，设 Andrew 取得数是 a_1,a_2,a_3，Jerry 取得数是 b_1,b_2,b_3。
即题目问 a_1 > b_1, a_2 > b_2，但 a_1+a_2+a_3<b_1+b_2+b_3 的概率是多少。
对于最后要求的式子 a_1+a_2+a_3<b_1+b_2+b_3 进行变形：
考虑暴力，暴力就是枚举 $c_1$、$c_2$、$c_3$ 的值，再判断符不符合题目要求，再进行计算概率。
如何优化？
对式子继续转化。得 $-(c_1 + c_2) > c_3$。
而 $c_1,c_2$ 的范围是固定的，$1\le c_1,c_2 \le 4999$。就可以枚举 $c_1,c_2$。且此时 $c_3$ 的范围也是固定的，$-4999 \le c_3 < -(c_1 + c_2)$。因为此时 $c_3$ 的上界和下界都已确定，所以就可以进行前缀和优化。
时间复杂度：$O((n + w)^2 + n)$，其中 $w$ 代表值域范围。
code：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int a[2009];
long double f[10009];
long double d[10009];
long double ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) continue;
f[a[i] - a[j] + 5000]++; // 进行下标偏移
}
}
for(int i = 1; i <= 10000; i++) {
f[i] /= (long double)((n - 1) * n / 2.0);
d[i] = d[i - 1] + f[i];
}
for(int i = 5001; i <= 9999; i++) {
for(int j = 5001; j <= 9999; j++) {
if(5000 - (i + j - 10000) - 1 < 0) continue;
ans += f[i] * f[j] * d[5000 - (i + j - 10000) - 1];
}
}
printf("%.5291Lf", ans);
return 0;
} // I am a deep well ice
```