比赛

 (mat.pas/c/cpp)

【问题描述】

    有两个队伍A和B，每个队伍都有n个人。这两支队伍之间进行n场1对1比赛，每一场都是由A中的一个选手与B中的一个选手对抗。同一个人不会参加多场比赛，每个人的对手都是随机而等概率的。例如A队有A1和A2两个人，B队有B1和B2两个人，那么(A1 vs B1,A2 vs B2)和(A1 vs B2,A2 vsB1)的概率都是均等的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

    37

    15

【样例输出】

    20.0

【数据规模】

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

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

 

∑(a[i]-b[i))^2

注意后缀数要在排序后T_Y

另外C++要用long double ---但是不能用.lf占位符

要用如下的格式

cout.setf(ios::fixed);
	cout.precision(1);



	cout<<ans/n<<endl;

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
long long n,a[MAXN],b[MAXN],sumb[MAXN],sumb2[MAXN];
int main()
{
    freopen("mat.in","r",stdin);
    freopen("mat.out","w",stdout);

    scanf("%d",&n);
    sumb[0]=sumb2[0]=0;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
	}
    sort(a+1,a+1+n);
	for (int i=1;i<=n;i++)
    {
        cin>>b[i];
}
    sort(b+1,b+1+n);

	for (int i=1;i<=n;i++)
	{
		sumb[i]=sumb[i-1]+b[i];
        sumb2[i]=sumb2[i-1]+b[i]*b[i];
	}


	long double ans=0.0;


	for (int i=1;i<=n;i++) cout<<sumb[i]<<' ';
	cout<<endl;
	int r=0;
    for (int i=1;i<=n;i++)
    {
        while (r<n&&a[i]>b[r+1]) r++;


        ans+=a[i]*a[i]*(2*r-n);
        ans+=2*sumb2[r]-sumb2[n];

        ans-=2*a[i]*(2*sumb[r]-sumb[n]);

        /*
		long double tmp=0.0;
        //cout<<r<<endl;

		tmp+=r*a[i]*a[i]-2*a[i]*sumb[r]+sumb2[r];
        cout<<tmp<<endl;

		tmp-=(n-r)*a[i]*a[i]-2*a[i]*(sumb[n]-sumb[r])+sumb2[n]-sumb2[r];
        tmp/=n;

        ans+=tmp;


//		cout<<ans;
	*/
    }

//	cout<<ans<<endl;

	cout.setf(ios::fixed);
	cout.precision(1);



	cout<<ans/n<<endl;



//  while (1);
    return 0;
}