Fireworks 期望，几何分布，概率，三分（2020.12.南京）

题意 ：

• n分钟做一个烟花，每个烟花有$p\ast 10^{-4}$的概率成功，每次做完一个烟花，可以选择继续做，或者花m分钟把之前做的所有剩下的都放掉，如果有至少一个成功，就去休息，求去休息的最小期望时间

思路 ：

• 因为每次都是集中释放做好的，所以可以假设每制作k个烟花后释放一次，直到出现一个成功为止，求当前期望花费，这就变成了一个典型的几何分布问题
• 几何分布 是离散型概率分布。其中一种定义为：在n次伯努利试验中，试验k次才得到第一次成功的机率。详细地说，是：前k-1次皆失败，第k次成功的概率。它的期望为1/p
• 每轮的时间开销为$k\ast n+m$，至少成功释放一个的概率为$(1-(1-p{)}^k)$，根据几何分布公式得期望为$\frac{1}{(1-(1-p{)}^k)}$，乘以每轮开销得期望时间花费为$\frac{k\ast n+m}{(1-(1-p{)}^k)}$
• 对这个式子打表或者求二阶导可知这是个单峰的凹函数，直接三分即可

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> using namespace std;typedef long long ll; typedef pair<int, int> PII;#define endl '\n' #define fi first #define se second #define push_back #define rep(i, l, r) for (ll i = l; i <= r; i ++ )long double calc(int k, int n, int m, long double p) {return ((long double)k * n + m) / ((long double)1.0 - pow(1.0 - p, k)); }void solve() {int n, m;long double p;cin >> n >> m >> p;p /= 10000;int l = 1, r = 1000000001;while (l < r){int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;long double t1 = calc(m1, n, m, p), t2 = calc(m2, n, m, p);if (t1 < t2) r = m2 - 1;else l = m1 + 1;}printf("%.10Lf\n", calc(l, n, m, p)); }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; }

总结

以上是生活随笔为你收集整理的Fireworks 期望，几何分布，概率，三分（2020.12.南京）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。