P9627 [ICPC2020 Nanjing R] Fireworks 题解

不难看出一个结论，最佳决策一定是我做了 \(a\) 个烟花后测试一波（此时没有烟花放了是吧，我们可以认为回到了一开始一个烟花都没做），再做了 \(a\) 个烟花再测试一波，以此类推。

这个时候我们考虑，一个烟花失败的概率是 \(1-p\)，那么一个烟花成功的概率是 \(1-(1-p)\)，\(a\) 个烟花成功的概率是 \(1-(1-p)^a\)。

再考虑一下，做 \(a\) 的烟花所需的时间（包括测试）是 \(m+an\)，综合一下我们可以列出一个计算期望时间的函数：

\[ f(a)=\dfrac{m+an}{1-(1-p)^a} \]

这个问题就转化成了求 \(f(a)\) 的最小值（\(a\in \N_+\)），很显然这是单调的对吧（因为你做越多烟花时间肯定越多），直接快乐二分。

using ll = long long;
using ld = long double;

constexpr static ll N = 2e9 + 11;
constexpr static ld Eps = 1e-7;
ll T, n, m, l, r;
ld p;

void solve() {
    std::cout << std::fixed << std::setprecision(10);
    auto calc = [&](ll x) {
        return ((ld)m + (ld)x * n) / ((ld)1.0 - fpow((ld)1.0 - p, x));
    }; // 计算期望时间的函数，就是上文中的 f(a)
    for(std::cin >> T; T--; [&](){
        std::cin >> n >> m >> p;
        p *= 1e-4; // 注意输进来的 p 要乘 1e-4
        l = 0, r = N;
        while(l < r) {
            ll mid = (l + r) >> 1;
            if (calc(mid + 1) - calc(mid) < Eps)
                l = mid + 1;
            else
                r = mid;
        }
        std::cout << calc(l) << '\n'; // 注意是左端点
    }());
}

P9627 [ICPC2020 Nanjing R] Fireworks 题解

评论