「Codeforces 1010A」Fly - 二分答案

建议访问原文出处，获得更佳浏览体验。
原文出处：https://hyp1231.github.io/2018/07/28/20180728-cf1010a/

题意

有 n$n$ 个行星，标号 1∼n$1\sim n$。飞行器从 1$1$ 出发，经过 2,3,…,n−1$2,3,\dots ,n-1$ 到达 n$n$，再从 n$n$ 出发到达 1$1$。
飞行器重 m$m$ 吨，且其携带的燃油也有重量。每次飞行器从行星 i$i$ 起飞，每消耗 1$1$ 吨燃油可以支持 ai$a_i$ 的重量；每次飞行器降落在行星 i$i$，每消耗 1$1$ 吨燃油可以支持 bi$b_i$ 的重量。只有飞行器拥有可以支撑当前总重量（飞行器重量 +$+$ 当前燃油重量）的燃油时，才可以成功起飞或降落。可以认为起飞和降落瞬间完成。
求旅程开始时携带燃油的最小吨数。

链接

Codeforces 1010A

题解

记在某次起飞 / 降落前，有燃油 w$w$ 吨。
首先考虑，如果某个 ai$a_i$ 或 bi$b_i$ 为 1$1$，则本次所需燃油数为 m+w>w$m+w>w$，不合法。因此先判断输入中是否存在 1$1$，若存在，则直接输出 −1$-1$。

考虑这个问题对应的判断问题。假设旅程开始前，共有 W$W$ 吨燃油。则我们可以直接遍历这个旅程的每次起飞和降落，判断开始前的 W$W$ 吨燃油是否足够。判定问题的时间复杂度为 O(n)$O(n)$。且对于单调增的 W$W$，必然会存在一个值作为能否完成旅程的分界线。（单调性，满足二分条件）

因此我们可以二分这个 W$W$，对每个确定的 W$W$ 判定是否可以完成旅途。当二分的间距小于精度时，输出这个 W$W$。

代码

#include <iostream>
#include <cmath>
#include <iomanip>

const int N = 1024;
const double EPS = 2e-7;    // 精度，1e-7 TLE

int n, m, a[N], b[N];

bool ok(double w) {
    double tot = m + w;
    for (int i = 0; i < n; ++i) {
        tot -= tot / a[i];  // 起飞
        if (tot < m && fabs(tot - m) > EPS) return false;
        int d = (i + 1) % n;
        tot -= tot / b[d];
        if (tot < m && fabs(tot - m) > EPS) return false;
    }
    return true;
}   // 判定问题

double solve(double l, double r) {
    double mid = (l + r) / 2;
    if (fabs(l - r) < EPS) return mid;
    if (ok(mid)) return solve(l, mid);
    else return solve(mid, r);
}   // 二分

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

    std::cin >> n >> m;
    bool flag = false;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] == 1) flag = true;
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
        if (b[i] == 1) flag = true;
    }
    if (flag) { // a 或 b 中存在 1
        std::cout << -1 << std::endl;
        return 0;
    }

    std::cout << std::setprecision(8) << solve(EPS, 1e9) << std::endl;

    return 0;
}