首页 > 其他 > 详细

JZOJ 3055. 【NOIP2012模拟10.27】比赛

时间:2019-03-09 14:31:27      阅读:196      评论:0      收藏:0      [点我收藏+]

题目

Description

 


有两个队伍AB,每个队伍都有n个人。这两支队伍之间进行n11比赛,每一场都是由A中的一个选手与B中的一个选手对抗。同一个人不会参加多场比赛,每个人的对手都是随机而等概率的。例如A队有A1A2两个人,B队有B1B2两个人,那么(A1 vs B1,A2 vs B2)(A1 vs B2,A2 vs B1)的概率都是均等的50%


每个选手都有一个非负的实力值。如果实力值为XY的选手对抗,那么实力值较强的选手所在的队伍将会获得(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
 

Data Constraint

 
 

Hint

 


对于30%的数据,n50


对于100%.,n50000;A[i],B[i]50000

 

分析

    利用公式算出每个人的期望  

   显然任意两个人相遇的概率是相等的,=两人第一场相遇的概率+两人第一场不相遇的概率*两人第二场相遇的概率+……。

 

代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 long long a[100001],b[101001],sum[100001],summ[100001];
 6 long long ans=0,cs;
 7 int n;
 8 int main ()
 9 {
10     
11     cin>>n;
12     for (int i=1;i<=n;i++)
13         cin>>a[i];
14     for (int i=1;i<=n;i++)
15         cin>>b[i];
16     sort(a+1,a+1+n);
17     sort(b+1,b+1+n);
18     for (int i=1;i<=n;i++)
19     {
20         sum[i]=sum[i-1]+b[i];
21         summ[i]=summ[i-1]+b[i]*b[i];
22     }
23     long long j=0;
24     for (int i=1;i<=n;i++)
25     {
26         while (a[i]>b[j]&&j<=n) j++;
27         ans+=(j-1)*a[i]*a[i]-2*a[i]*sum[j-1]+summ[j-1];
28         ans-=((n-j+1)*a[i]*a[i]-2*a[i]*(sum[n]-sum[j-1])+summ[n]-summ[j-1]);
29     }
30     double s=(double)(ans)/(double)(n);
31     printf("%.1f",s);
32 }

 

 

JZOJ 3055. 【NOIP2012模拟10.27】比赛

原文:https://www.cnblogs.com/zjzjzj/p/10500550.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!