[ICPC2020 Nanjing R] Fireworks 题解

· · 题解

式子写出来，题就很显然。

考虑在做了 x 个烟花后放掉是最优的，如果放掉之后再也没有好烟花放了，那么状态可以看做回到了起始位置，那也还得做 x 个烟花。所以每一次做烟花的数是固定的。

那么就假设你做了 x 个烟花，然后把他们全部放掉。

根据题意，花费的时间为 xn+m，每轮好烟花的概率为 1-(1-p)^x。

高中数学选修三告诉我们，这是一个几何分布，则他的期望时间 T 为：

T=\dfrac{xn+m}{1-(1-p)^x}

导一下发现这是个单峰函数，那么直接三分就可以得到答案。

代码：

#include <bits/stdc++.h>
using namespace std;
double n, m, p;
inline double qp(double a, int b) { double ans = 1; for(; b; a *= a, b >>= 1) if(b & 1) ans *= a; return ans; }
inline double f(int k) { double t = 1.0 - qp(1.0 - p, k); return (!t) ? (double)0x3f3f3f3f : (k * n * 1.0 + m) / t; }
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T, mid1, mid2; cin >> T;
    for(double f1, f2; T; -- T) {
        cin >> n >> m >> p, p *= 1e-4;
        int l = 1, r = 0x3f3f3f3f; double res = (double)0x3f3f3f3f3f3f3f3f;
        while(r > l) mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3, f1 = f(mid1), f2 = f(mid2), res = min(res, min(f1, f2)), (f1 < f2) ? (r = mid2 - 1) : (l = mid1 + 1); 
        cout << fixed << setprecision(10) << res << endl;
    }
}