4852 -- 【模拟试题】比赛
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的得分的期望值。
Input
第一行一个数n表示两队的人数为n。
第二行n个整数，第i个数A[i]表示队伍A的第i个人的实力值。
第三行n个整数，第i个数B[i]表示队伍B的第i个人的实力值。
Output
输出仅包含一个实数表示A期望赢B多少分。答案保留到小数点后一位（注意精度）。
Sample Input
2
3 7
1 5
Sample Output
20.0
Hint
【数据规模】
对于30%的数据，n≤50。
对于100%的.据,n≤50000;A[i],B[i]≤50000。
其实题目对于这个所谓的期望的求法已经说得很清楚了，就是算两个队各个队员的差值乘以概率累加，这样说得很抽象，举个例子。
A队：A B C
B队：a b c
为了叙述方便，这里设A>B>C>a>b>c
那么期望为:
(A-a)^2/3+(B-b)^2/3+(C-c)^2/3
再假设这里a>A，那么期望为：
-(A-a)^2/3+(B-b)^2/3+(C-c)^2/3
这里注意一点，为了保证精度，把分母放在最后除。
这样一个O(n^2)的算法就可以得到了：枚举每个A队员，再枚举每个B队员，可以得到期望。
优化？
//很多这样需要n^2优化至近似n的，大都有排序
我们注意到n^2的枚举有一个地方太累了：它每次都去比较A队员和B队员的大小，再加起来，如果我们对A,B队分别排序，就可以找到一个边界就结束，再者，这个边界还可以用二分加速。
举个例子。
Team A: A B C D E F
Team B:a b c d e f
两个数列都是增序排序，现在枚举到队员A，找到B队中的c队员比他大，那么根据 (a-b)^2=a^2-2ab+b^2 容易知道前面肯定有2个a^2,2个b^2，后面有4个-a^2,4个-b^2.现在再讨论"ab",根据结合律，有sigma(ab)=a*sigma(b)，这里对于b的处理就跟前面的b^2是一致的----记录前缀和。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
using namespace std;
typedef long long ll;
ll a[200005]= {0},b[2000005]= {0};
ll n,sum1[200005]={0},sum2[2000005]={0};
int main() {
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
{
sum1[i]=sum1[i-1]+b[i];
sum2[i]=sum2[i-1]+b[i]*b[i];
}
ll pointer=0;
long double ans=0;
for(int i=1;i<=n;i++)
{
while(a[i]>b[pointer+1]&&pointer<n)pointer++;
ans+=a[i]*a[i]*(2*pointer-n); //前面pointer个，后面n-pointer个
ans+=2*sum2[pointer]-sum2[n];
ans-=2*a[i]*(2*sum1[pointer]-sum1[n]);
}
cout<<fixed<<setprecision(1)<<(ans/n);
return 0;
}