Fireworks(2020 ICPC南京)
程序员文章站
2022-03-30 16:40:24
...
题意:
你每做一个烟花要n分钟,释放已做好的所有烟花需要m分钟,每只烟花成功释放的概率为p。问你在采取最优策略的前提下,直到成功释放第一个烟花时最小的期望时间花费。
题解:
最佳策略是:每次集中做法,然后集中释放。所以我们设每制作k个烟花后集中释放一次,直到某次释放时成功出现一次为止。求当前期望时间花费,这是一个典型的几何分布
每轮的时间开销为:T = k * n + m,每轮至少成功释放烟花的概率为P,P怎么求?一次都不成功的概率为(1 - p)k,那么P=1-(1-p)k,根据几何分布公式期望为E = 1/P,乘以每轮开销的期望时间花费为T * E
这是一个单峰的凹函数,通过三分找答案
代码:
#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b);
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
long double fun(int k,int n,int m,long double p){
return ((long double)k*n+m)/((long double)1.0-pow(1.0-p,k));
}
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
double p;
cin>>n>>m>>p;
p*=(1e-4);
int l=1,r=0x3f3f3f3f;
while(l<r){
int mid1=l+(r-l)/3;
int mid2=r-(r-l)/3;
if(fun(mid1,n,m,p)<fun(mid2,n,m,p))r=mid2-1;
else l=mid1+1;
}
printf("%.10Lf\n",fun(l,n,m,p));
}
}
推荐阅读
-
南京大学排名2021最新排名-附2020年录取分数线(含山东、河南多省)
-
2021年正常人考南京大学有多难?南京大学各省录取分数线2020
-
2020南京所有二本大学排名:南京最好考的二本学校是哪些?
-
南京大学计算机科学与技术系暨人工智能学院2020年本科生开放日报名通知
-
南京大学是顶尖大学吗?考上南京大学算学霸吗?(内含2020年录取分数线及位次)
-
ICPC NEAU Programming Contest 2020 D 旅游(单调栈)
-
2020ICPC·小米 网络选拔赛热身赛-A.ABBA
-
A. Arena of Greed(博弈+贪心)2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest
-
2020ICPC·小米网络选拔赛第一场 J.Matrix Subtraction
-
2020ICPC·小米 网络选拔赛第一场 D - Router Mesh(求删掉割点后的连通块数)