「NOIP模拟赛」比赛
「问题描述」
有两个队伍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弱的里面最强的人，维护实力值的前缀和，实力值平方的前缀和即可算出期望。
显然指针只可能向右移动，所以这一步是线性的。
我直接用了个二分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; ll a[50005],b[50005]; ll s1[50005],s2[50005]; ll ans1,ans2; int find(int x) { int l=1,r=n,ans=0; while(l<=r) { int mid=(l+r)>>1; if(b[mid]<=x)l=mid+1,ans=mid; else r=mid-1; } return ans; } int main() { //freopen("mat.in","r",stdin); //freopen("mat.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); sort(b+1,b+n+1); for(int i=1;i<=n;i++) { s1[i]=s1[i-1]+b[i]; s2[i]=s2[i-1]+b[i]*b[i]; } for(int i=1;i<=n;i++) { int t=find(a[i]); ans1+=t*a[i]*a[i]+s2[t]-2*s1[t]*a[i]; ans2+=(n-t)*a[i]*a[i]+(s2[n]-s2[t])-2*(s1[n]-s1[t])*a[i]; } printf("%.1lf",(double)(ans1-ans2)/n); return 0; } |
Subscribe
计数器 9854664
OI 课件=>
OI 课件=>