题目大意
有
n
n
n个选手参加比赛，比赛有两道题。
对于第一题，第
i
i
i个选手有
50
%
50\%
50%的可能拿到
a
i
,
1
a_{i,1}
ai,1分，有
50
%
50\%
50%的可能拿到
0
0
0分。
对于第二题，第
i
i
i个选手有
50
%
50\%
50%的可能拿到
a
i
,
2
a_{i,2}
ai,2分，有
50
%
50\%
50%的可能拿到
0
0
0分。
一名选手的排名为分数比他高的选手的个数加1。求每个选手的期望排名。
题解
每个选手总共可能有4种成绩，每种成绩都为
1
4
\dfrac 14
41的概率。
先只考虑选手
a
a
a的一种成绩对选手
b
b
b的一种成绩的贡献。如果选手
a
a
a的一种成绩大于选手
b
b
b的一种成绩，那么在这种情况下
a
a
a对
b
b
b排名的贡献为1，而出现这种情况的概率为
1
16
\dfrac{1}{16}
161，所以这种情况对
b
b
b的期望排名的贡献为
1
16
\dfrac{1}{16}
161。
我们可以把每种选手的各种成绩放在一起排序。选手
i
i
i的期望排名就是，对于选手
i
i
i的各个成绩，在这个成绩之前的不是选手
i
i
i的成绩的成绩的数量之和乘
1
16
\dfrac{1}{16}
161，最后再加1。
因为
a
a
a的值比较小，所以可以用桶来维护。
时间复杂度为
O
(
n
+
k
)
O(n+k)
O(n+k)，其中
k
k
k为桶的大小。
code
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[100005][2],z[200005];
double pt;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i][0],&a[i][1]);
++z[0];
++z[a[i][0]];
++z[a[i][1]];
++z[a[i][0]+a[i][1]];
}
for(int i=20000;i>=0;i--){
z[i]+=z[i+1];
}
for(int i=1;i<=n;i++){
ans=z[1]+z[a[i][0]+1]+z[a[i][1]+1]+z[a[i][0]+a[i][1]+1];
if(a[i][0]!=0) --ans;
if(a[i][1]!=0) --ans;
if(a[i][0]+a[i][1]!=0) --ans;
if(a[i][1]!=a[i][0]) --ans;
if(a[i][0]+a[i][1]!=a[i][0]) --ans;
if(a[i][0]+a[i][1]!=a[i][1]) --ans;
pt=1.0*ans/16+1;
printf("%.6f\n",pt);
}
return 0;
}