题意:n个人去竞拍一件商品,下面给出n个区间表示每个人出的价是区间中随机的一个数(概率均等)则第一名需要付的钱是第二名的竞拍价格(允许并列第一名)求支付的钱的期望。
思路:参考九野巨的博客:http://blog.csdn.net/qq574857122/article/details/43640187
/********************************************************* file name: C.cpp author : kereo create time: 2015年02月08日 星期日 22时26分08秒 *********************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #include<stack> #include<cmath> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int sigma_size=26; const int N=100+50; const int MAXN=10000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=1000000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair<int, int> #define mk(x,y) make_pair((x),(y)) int n; int l[MAXN],r[MAXN]; double solve1(int x){ //第一 >x int flag,tag; double ans=0; for(int i=1;i<=n;i++){ if(r[i]<=x) continue; flag=1,tag=0; for(int j=1;j<=n;j++){ if(i == j) continue; if(l[j]>x){ flag=0; break; } if(l[j]<=x && x<=r[j]) tag=1; } if(flag == 0 || tag == 0) continue; double res=(r[i]-max(x,l[i]-1))*1.0/(r[i]-l[i]+1); double ans1=1.0,ans2=1.0; //ans1为全部<=x的概率,ans2为全部<x的概率 for(int j=1;j<=n;j++){ if(i == j) continue; if(x>=l[j] && x<=r[j]){ ans1*=(x-l[j]+1)*1.0/(r[j]-l[j]+1); ans2*=(x-l[j])*1.0/(r[j]-l[j]+1); } } ans+=(ans1-ans2)*res; } return ans; } double solve2(int x){ //第一 =x int flag=0; for(int i=1;i<=n;i++) if(x<l[i]) return 0; else if(l[i]<=x && x<=r[i]) flag=1; if(flag == 0) return 0; double ans=1.0,ans1=1.0,ans2=0.0; //ans为全部<=x的概率,ans1为全部<x的概率,ans2为有一个为x,其余<x的概率 for(int i=1;i<=n;i++){ if(l[i]<=x && x<=r[i]){ ans*=(x-l[i]+1)*1.0/(r[i]-l[i]+1); ans1*=(x-l[i])*1.0/(r[i]-l[i]+1); } } for(int i=1;i<=n;i++){ if(l[i]<=x && x<=r[i]){ double tmp=1.0/(r[i]-l[i]+1); for(int j=1;j<=n;j++){ if(l[j]<=x && x<=r[j]){ if(i == j) continue; tmp*=(x-l[j])*1.0/(r[j]-l[j]+1); } } ans2+=tmp; } } return ans-ans1-ans2; } int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]); double ans=0; for(int i=1;i<=10000;i++){ ans+=solve1(i)*i; //第一人出价>x ans+=solve2(i)*i; //第一人出价=x } printf("%.10f\n",ans); } return 0; }