描述 Description
有两个队伍 A 和 B，每个队伍都有 n 个人。这两支队伍之间进行 n 场 1 对 1 比赛，每一场都是由 A 中的一个选手与 B 中的一个选手对抗。同一个人不会参加多场比赛，每个人的对手都是随机而等概率的。例如 A 队有 A1 和 A2 两个人，B 队有 B1 和 B2 两个人，那么 (A1 vs B1,A2 vs B2) 和(A1 vs B2,A2 vs B1)的概率都是均等的 50%。
每个选手都有一个非负的实力值。如果实力值为 X 和 Y 的选手对抗，那么实力值较强的选手所在的队伍将会获得(X-Y)^2 的得分。
求 A 的得分减 B 的得分的期望值。
输入格式 InputFormat
第一行一个数 n 表示两队的人数为 n。
第二行 n 个数，第 i 个数 A[i]表示队伍 A 的第 i 个人的实力值。
第三行 n 个数，第 i 个数 B[i]表示队伍 B 的第 i 个人的实力值。
输出格式 OutputFormat
输出仅包含一个实数表示 A 期望赢 B 多少分。答案保留到小数点后一位（注意精度）。
样例输入 SampleInput
2
3 7
1 5
样例输出 SampleOutput
20.0
来源 Source
2014-10-5 NOIP 模拟赛 by lwher
代码 Code
根据期望的和 = 和的期望，只需把 A 队每个人的期望得分减去 B 队每个人的期望得分即为答案。
A 队某人 X 的期望得分为 $((A_{x}-B_{y})^{2}*P(A_{x},B_{y})) $（其中 y 为 B 队中实力低于 X 的人，P 代表 X 和 Y 相遇的概率）。
显然任意两个人相遇的概率是相等的，= 两人第一场相遇的概率 + 两人第一场不相遇的概率 * 两人第二场相遇的概率 +……。
排序后只需枚举一个人 i，用一个指针指着另一队中实力比 i 弱的里面最强的人，维护实力值的前缀和，实力值平方的前缀和即可算出期望。
显然指针只可能向右移动，所以这一步是线性的。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int a[50005],b[50005];
long long sum[50005],sum2[50005];
long double ans;
int main()
{
cout.setf(ios::fixed);
cout.precision(1);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) scanf("%d",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for (i=1;i<=n;i++) sum[i]=sum[i-1]+b[i],sum2[i]=sum2[i-1]+(long long)b[i]*b[i];
t=0;
ans=0.0;
for (i=1;i<=n;i++)
{
while (t<n && a[i]>b[t+1]) t++;
ans+=(long long)a[i]*a[i]*(t*2-n);
ans+=(long long)sum2[t]*2-sum2[n];
ans-=(long long)a[i]*2*(sum[t]*2-sum[n]);
}
ans/=n;
//cout<<ans<<endl;
printf("%.1lf\n",(double)ans);
return 0;
}