[原创]51Nod-算法马拉松23 B 谷歌的恐龙 [概率期望]【数学】

Tabris

CSDN数学51nod

发布于：2017年4月21日

次浏览

[原创]51Nod-算法马拉松 23 B 谷歌的恐龙 [概率期望]【数学】

2017-04-21 16:27:27 Tabris_ 阅读数：1004

博客爬取于 2020-06-14 22:40:56
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70328966

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1765
————————————————————————————————————————————
1765 谷歌的恐龙
基准时间限制：1 秒 空间限制：1048576 KB 分值： 80 难度：5 级算法题 收藏 关注
相信网络不好的选手一定很熟悉 Chrome 里面那个恐龙的游戏，这个题目就是根据那个游戏简化得来的。
给出一个正整数 n，把恐龙的跳跃简化成一个[0,n)的随机数，再给出一个正整数 m，把障碍简化为[0,n)中 m 个不同的的整数，把分数简化成所有生成的随机数的和。
把整个游戏简化为，每次生成一个[0,n)的随机数，如果这个随机数和给出的 m 个数字中的其中一个数字相等，那么就停止生成随机数，否则继续生成，求出所有生成的数的和的期望。
Input
第一行两个正整数 n(1<=n<=10000000),m(1<=m<=n)
第二行 m 个整数 a_i 表示障碍(0<=a_i< n)
Output
一行一个实数 E 表示期望，保留 6 位小数。
注意了本题没有 SPJ，必须和答案完全相同才能通过本题

样例解释：当生成的是 0 的时候继续，生成的是 1 的时候停止
E=1/2+1/4+.....=1
Input 示例
2 1
1
Output 示例
1.000000
————————————————————————————————————————————

本题就是简单的求期望

设 x 为选择的数的期望和

E = \dfrac{m}{n}\times \dfrac{x}{m} + \dfrac{n-m}{n}\times \Big( \dfrac{\frac{n\times (n-1)}{2}-x}{n-m}+E\Big)
\Rightarrow E = \dfrac{x}{n} + \dfrac{\frac{n\times (n-1)}{2}-x}{n}+\dfrac{n-m}{n}\times E
\Rightarrow E - \dfrac{n-m}{n}\times E = \dfrac{x+\frac{n\times (n-1)}{2}-x}{n}
\Rightarrow E\times \dfrac{m}{n} = \dfrac{\frac{n\times (n-1)}{2} }{n}
\Rightarrow E\times m = \dfrac{n\times (n-1)}{2}
\Rightarrow E = \dfrac{n\times (n-1)}{2\times m}

然后就....

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12

# include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N = 200000+7;

int main() {
    LL n, m;
    scanf("%lld%lld", &n, &m);
    printf("%.6f\n", n * 1.0 * (n - 1) / 2 / m);
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

数学

算法