题意:
一个袋子里装了n个球,每个球都有编号。甲乙二人从每次随机得从袋子里不放回的取出一个球,如果甲取出的球比乙取出的球编号大则甲胜,否则乙胜。保证球的编号xi各不相同。每轮比赛完了之后把取出的两球放回。求甲在前两轮比赛胜利,乙在最后一轮比赛胜利的情况下,乙所有球的和大于甲所有球的和概率。
其中 2<=n<=2000 1<=xi<=5000
思路:
从xi的范围入手,记录某一轮中两个人的差值,然后再求解出一个后缀和,代表某轮比赛中其中一人比另一人大x以上的概率。这样枚举前两轮的差值求和,直接在存后缀和的数组里找到,然后乘完了累加。
#include<bits/stdc++.h> using namespace std; int jilu[2005]; double dp[5005]; double aft[5005]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&jilu[i]); } sort(jilu,jilu+n); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ dp[jilu[j]-jilu[i]]++; } } double tmp=n*(n-1)/2,ans=0; for(int i=0;i<=5000;i++){ dp[i]/=tmp; } // double ans=0; for(int i=5000;i>=0;i--){ aft[i]=aft[i+1]+dp[i+1]; } for(int i=1;i<=5000;i++){ for(int j=1;j<=5000;j++){ if(i+j>=5000) break; ans+=dp[i]*dp[j]*aft[i+j]; } } printf("%lf ",ans); }