「NOIP模拟赛」比赛

2014年10月6日3,6220

「问题描述」

有两个队伍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的得分的期望值。

「输入格式」

第一行一个数n表示两队的人数为n。

第二行n个数,第i个数A[i]表示队伍A的第i个人的实力值。

第三行n个数,第i个数B[i]表示队伍B的第i个人的实力值。

「输出格式」

输出仅包含一个实数表示A期望赢B多少分。答案保留到小数点后一位(注意精度)

「样例输入」

2

3 7

1 5

「样例输出」

20.0

「数据规模」

对于30%的数据,n≤50。

对于100%的.据,n≤50000;A[i],B[i]≤50000。

题解

排序后只需枚举一个人i,用一个指针指着另一  队中实力比i弱的里面最强的人,维护实力值的前缀和,实力值平方的前缀和即可算出期望。

显然指针只可能向右移动,所以这一步是线性的。

我直接用了个二分

 

avatar
  Subscribe  
提醒