Fireworks 期望 + 概率 ICPC2020 上海

Fireworks 期望 + 概率

题目大意:

制作一个火焰花费 n 分钟,这个火焰是完美的概率是 \(p\) ,点亮所有制作的火焰花费的时间是 m 分钟,问成功点亮一个完美火焰的最短时间是多少。

题解:

这个题目其实不是很难,但是我不会写,对我来说真的好难啊,我真的一点也不会期望概率,需要好好补一下。

花费 \(x\) 次制作一个完美的火焰的概率是:\(\frac{1}{1-(1-p)^{x}}\) ,花费的时间是:\(\frac{n*x+m}{1-(1-p)^{x}}\) ,这个可用三分解决。

这个题目,我又wa了很多发,原因是我在 f 函数里面的 n*x,没有在前面乘以1.0

以后碰到要乘以1.0 或者是1ll 的一定要在开头乘!!!!

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 5e5+10;
typedef long long ll;
const double EPS = 1e-9;
int n,m,P;
double q;
double f(int x){
    return (1.0*n*x+1.0*m)/(1.0-pow(q,x));
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d",&n,&m,&P);
        q =1 - P*0.0001;
        ll l = 1,r = 1e9;
        double lans = f(l),rans = f(r);
        while(l < r) {
            ll lmid = l + (r - l) / 3;
            ll rmid = r - (r - l) / 3;
            lans = f(lmid),rans = f(rmid);
            // 求凹函数的极小值
            if(lans <= rans) r = rmid - 1;
            else l = lmid + 1;
        }
        printf("%.10f\n",min(lans,rans));
    }
}
上一篇:UCF Local Programming Contest 2016


下一篇:[比赛][ICPC2020] 2020ICPC亚洲区域赛网上模拟赛