题目链接
题目大意
每次做一个烟花要n分钟 点燃当前所有烟花要m分钟
每个烟花成功燃放的概率是p
每次选择做完k个烟花后进行点燃当前烟花
直到有烟花成功燃放为止
你要选择一个最佳的k 让时间期望最小
题目思路
每k个烟花一起燃放至少有一个成功燃放的概率是
PP=(1-(1-p)^k)
由于当放成功烟花就可以结束可以很轻松的推出这是一个几何分布
那么几何分布的期望 (第几次能够抽中)
为 E=1/PP
那么期望时间为
ET=E*T=T/PP=(k*n+m)/(1-(1-p)^k)
打表可知 随着k的改变ET是个 单峰凹函数
也可以数学推导得出结论但是我高数还给老师了就打表了
使用三分得到答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
double n,m,p;
int t;
double quickpow(double a,ll b)
{double ans=1;while(b>0){if(b&1){ans*=a;//ans%=mod1;}a*=a;//使用自乘来快速幂。//a%=mod1;b>>=1;}return ans;
}
double sol(int k)
{return (double(k)*n+m)/(1.0-quickpow(1.0-p,k));
}
int main()
{cin>>t;while(t--){cin>>n>>m>>p;int l=1,r=inf;p*=1e-4;while(l<r){int midl=l+(r-l)/3;int midr=r-(r-l)/3;if(sol(midl)<sol(midr)){r=midr-1;}else l=midl+1;}printf("%.6lf\n",sol(l));}return 0;
}