第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）F.Fireworks（概率+三分）

分析

这题是一道几何分布的问题，百度对于几何分布的解释：

做一个完美烟花的概率为 p ，我们可以算出 x 个烟花中含有完美的烟花的概率为 (1 - (1 - p)^x) ，则做出烟花个数的期望就为 1 / (1 - (1 - p)^x)，那么做出完美烟花的花费的期望就是 (x * n + m) / (1 - (1 - p)^x) ，这是一个凹函数，可以用三分找到答案。

代码

#include<bits/stdc++.h>
using namespace std;int n,m,p;
double q;double f(int x)
{
    return (1.0 * x * n + m) / (1.0 - pow(q, x));
}void solve()
{
    cin>>n>>m>>p;q = 1.0 - p * 1e-4;int l = 1,r = 1e9;double ans = min(f(l), f(r));while(l < r){
    int mar = (r - l) / 3;int fl = l + mar;int fr = r - mar;double ffl = f(fl);double ffr = f(fr);if(ffl <= ffr) r = fr - 1;else l = fl + 1;ans = min(ans, min(ffl, ffr));}printf("%.5lf\n",ans);
}int main()
{
    int t;cin>>t;while(t--){
    solve();}return 0;
}