2020icpc南京站F：Fireworks
南京站其余題目(點擊進入)
題目：
思路：
首先先來說明，每一次都是生產相同數量點燃，
原因：這是需要最優策略，假設k=9是最優策略，那么就要一直選擇9進行燃燒，
所以對于每次進行的燃燒，都要等到生產了k(9)個時才能進行一塊點燃，
假設每k個釋放一次，那么成功的概率為1-(1-p)^k（p=p*1e-4），
釋放幾次后可以得到完美的期望------幾何分布：
幾何分布：離散型概率分布，其中一種定義為：在n次伯努利試驗中，
試驗k次才得到第一次成功的概率，詳細的說，是：前k-1次皆失敗，
第k次成功的概率，
期望E(x)=1/p;(概率論公式，不再贅述)
所以可以得
f(k)=E(x)(kn+m) = (k*n+m)/[1-(1-p)^k]，
尋找最優解，最小值，猜測是開口向上的拋物線—驗證，
測驗1-10000的k看資料變化， 驗證------三分答案：
代碼
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
double n,m,p;
//優化冪運算;
double ksm(double a,int b){
double ans = 1;
while(b){
if(b&1) ans = ans*a;
a = a*a;
b>>=1;
}
return ans;
}
//計算f(k);
double f(int k){
double tmp = 1.0-ksm(1.0-p,k);
if(tmp == 0) return (double)0x3f3f3f3f;
return (k*n*1.0+m)/tmp;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lf%lf%lf",&n,&m,&p);
p*=(1e-4);
int l = 1,r = 0x3f3f3f3f;
double ans = (double)0x3f3f3f3f3f3f3f3f;
//取最大值，0x3f3f3f3f不夠，
//三分板子
while(r > l){
int lm = l+(r-l)/3,rm = r-(r-l)/3;
double f1 = f(lm),f2 = f(rm);
ans = min(ans,min(f(lm),f(rm)));
if(f(lm) < f(rm)){
r = rm-1;
}
else l = lm+1;
}
printf("%.10lf\n",ans);
}
return 0;
}
參考資料
三分知識點
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/240091.html
標籤：其他
上一篇：Java例外體系——（面試題）