2020ICPC南京站 F题 Firworks 几何分布 + 三分

传送门：https://ac.nowcoder.com/acm/contest/10272/F

题意

n分钟做一个烟花，m分钟放掉所有做完的烟花。p的概率制造出完美的烟花。问最少的期望时间可以做出完美的烟花。

思路

这个烟花只有是不是完美的两种，所以是几何分布。而几何分布的期望为$\frac{1}{p}$，所以我们需要知道一次性做多少个烟花可以做出完美的烟花。

假设我们制造出k个烟花，然后一次性花m分钟释放完，其中就有完美的烟花，所以我们的总时间为$(n*k+m)$，而存在完美烟花的概率为$1-(1-p)^k$,所以做出一个完美烟花的期望为$\frac{1}{1-(1-p)^k}$，乘上时间，总期望时间为$\frac{(n*k+m)}{1-(1-p)^k}$。

所以我们想知道这个k是多少。回答：三分答案。

因为总期望时间函数不是单调的，所以二分不行的，需要三分。 即三分答案，枚举k，刚开始的区间为[1,10000]。取最小ans即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;
ll n, m;
double p;

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

double Clac(int k) {
    return (k * n + m) / (1 - quick_pow(1 - p, k));
}

void solve() {
    int _; scanf("%d",&_);
    while(_--) {
        scanf("%lld%lld%lf",&n,&m,&p);
        p *= 0.0001;
        int l = 1, r = 100000;
        double ans = (n + m) / p;
        while(r - l >= 10) {
            int mid1 = l + (r - l) / 3;
            int mid2 = r - (r - l) / 3;
            if(Clac(mid1) < Clac(mid2)) r = mid2;
            else l = mid1;
        }
        for(int i = l;i <= r; i++) {
            ans = min(ans, Clac(i));
        }
        printf("%lf\n",ans);
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/25/2020-icpc-nanjing-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！