第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)F.Fireworks

传送门
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)F.Fireworks

题意:

每一个烟花爆炸成功的概率为p*0.0001,我们设最优策略为一次性燃放k个烟花,则k个烟火中至少有一个燃放成功的概率为 1 − ( 1 − p ) k 1-(1-p)^k 1−(1−p)k.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
ll n,m;
long double p;
long double f(ll x)
{
	return ((long double)x*1.0*n+m*1.0)/((long double)1.0-pow(1.0-p,x));
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>p;
		p *= 0.0001;
		int l = 1,r = 0x3f3f3f3f;
		while(l < r)
		{
			int midl = l+(r-l)/3;
			int midr = r-(r-l)/3;
			long double ansl = f(midl);
			long double ansr = f(midr);
			if(ansl < ansr)r = midr-1;
			else l = midl+1;
		}
		printf("%.10Lf\n",f(l));
	}
}
上一篇:力扣 - 剑指 Offer 45. 把数组排成最小的数


下一篇:45-关于深拷贝的一些问题