2020ICPC南京站F-Fireworks 题解

题目大意

你可以花费n点时间去制作一个烟花，可以任意做多少个，每个烟花有$p\times 10^{-4}$的概率是一个完美的烟花，你需要

花费m点时间去把你制作的所有烟花点燃，问至少点燃一个完美的烟花的最小期望值是多少。

解题思路

赛时这个题目连怎么求期望都没想到。。

更不用说想到三分了。

说实话，还是感觉自己太菜了，签到题都写了那么久，同题数我们都已经垫底了。。

需要提高思维速度了。

而且像概率这种东西，我们队没有会的。。

这就属于知识盲区了。

寒假要加油学了。

这题对于不同的一次制作数量k，可以得到一个关于k的期望函数$\Large \frac{1}{1-(1-p)^k}$,那么就可以得到花费的期望函数$\Large \frac {n*k+m}{1-(1-p)^k}$。

由打表或者求导可以看出是一个单峰的凹函数，用三分求峰值即可。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

ll n, m;
double p;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

double qpow(double a, int b) {
	double ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a *= a, b >>= 1;
	}
	return ans;
}

double cal(int k) {
	double ans = 1.0 * (n * k + m) / (1.0 - qpow(1.0 - p, k));
	return ans;
}

int main() {
	//ios::sync_with_stdio(0);
	//cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		cin >> n >> m >> p;
		int l = 0, r = 1e9;
		p /= 1e4;
		while (l < r) {
			int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
			if (cal(mid1) < cal(mid2))	r = mid2 - 1;
			else l = mid1 + 1;
		}
		printf("%.10f\n", cal(l));
	}
	return 0;
}