Codeforces 513C Second price auction 概率dp 求期望 - c++编程基础

TOP

Codeforces 513C Second price auction 概率dp 求期望

2015-07-20 17:19:41 来源: 作者: 【大中小】浏览:2次

Tags：Codeforces 513C Second price auction 概率期望

题目链接：点击打开链接

题意:

有n个人去竞拍一件商品，下面给出n个区间表示每个人出的价是区间中随机的一个数（概率均等)

则第一名需要付的钱是第二名的竞拍价格（允许并列第一名）

求支付的钱的期望。

思路:

枚举付的钱，然后求付这个钱的概率，相乘后求和即可。

对于确定支付x元

分类讨论一下：

1、第一名出价大于x

枚举第一名，然后剩下来的人至少一个人出x元，其他人出<=x，

P(剩下来的人一个人出x元，其他人出<=x) = P(剩下来的人出价<=x) - P(剩下的人出价

2、第一名出价等于x，则出价中至少有2个x

P(至少2人出x) = P(所有人出价<=x) - P(所有人出价

#include 
  
     
#include 
   
     #include 
    
      #include 
      #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            template 
           
             inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template 
            
              inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } using namespace std; typedef long long ll; const int N = 35; int n, a[N], l[N], r[N]; double work(int x){ double ans = 0; for (int i = 1; i <= n; i++){//显然只有一个第一名，枚举这个第一名 if (r[i] < x+1)continue; //他的出价<=x bool ok = true, hav = false; for (int j = 1; j <= n; j++) if (i != j){ if (l[j] <= x && x <= r[j])hav = true; if (x < l[j])ok = false; } if (ok == false || hav == false)continue; double p = (double)(r[i] - x) / (r[i] - l[i] + 1); p = min(p, 1.0); double len = 1, H = 1; for (int j = 1; j <= n; j++) { if (i != j && l[j] <= x && x <= r[j]){ len *= (double)(x - l[j] + 1) / (r[j] - l[j] + 1); H *= (double)(x - l[j]) / (r[j] - l[j] + 1); } } len -= H; ans += len * p; } return ans; } double work2(int x){ bool hav = false; for (int i = 1; i <= n; i++)if (x < l[i])return 0; else if (l[i] <= x && x <= r[i])hav = true; if (hav == false)return 0; double all = 1, one = 0, zero = 1; for (int i = 1; i <= n; i++){ if (l[i] <= x&&x <= r[i]){ all *= (double)(x - l[i] + 1) / (r[i] - l[i] + 1); zero *= (double)(x - l[i]) / (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 (i != j && l[j] <= x && x <= r[j]) tmp *= (double)(x - l[j]) / (r[j] - l[j] + 1); one += tmp; } } return (all - zero - one); } int main(){ while (cin >> n){ for (int i = 1; i <= n; i++)rd(l[i]), rd(r[i]); double ans = 0; for (int i = 1; i <= 10000; i++){//第二名出价为i ans += work(i) * i; //第一名出价大于i ans += work2(i) * i;//第一名出价=i } printf("%.10f\n", ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：LeetCode --- 41. First Missing ..	下一篇：HDU 3152 Obstacle Course(优先队..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: