Fireworks

題意：

你每做一個煙花要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));} }

總結

以上是生活随笔為你收集整理的Fireworks(2020 ICPC南京)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。