「Codeforces 1010A」Fly - 二分答案

建議通路原文出處，獲得更佳浏覽體驗。

原文出處：https://hyp1231.github.io/2018/07/28/20180728-cf1010a/

題意

有 n n 個行星，标号 1∼n1∼n。飛行器從 1 1 出發，經過 2,3,…,n−12,3,…,n−1 到達 n n ，再從 nn 出發到達 1 1 。

飛行器重 mm 噸，且其攜帶的燃油也有重量。每次飛行器從行星 i i 起飛，每消耗 11 噸燃油可以支援 ai a i 的重量；每次飛行器降落在行星 i i ，每消耗 11 噸燃油可以支援 bi b i 的重量。隻有飛行器擁有可以支撐目前總重量（飛行器重量 + + 目前燃油重量）的燃油時，才可以成功起飛或降落。可以認為起飛和降落瞬間完成。

求旅程開始時攜帶燃油的最小噸數。

連結

Codeforces 1010A

題解

記在某次起飛 / 降落前，有燃油 ww 噸。

首先考慮，如果某個 ai a i 或 bi b i 為 1 1 ，則本次所需燃油數為 m+w>wm+w>w，不合法。是以先判斷輸入中是否存在 1 1 ，若存在，則直接輸出 −1−1。

考慮這個問題對應的判斷問題。假設旅程開始前，共有 W W 噸燃油。則我們可以直接周遊這個旅程的每次起飛和降落，判斷開始前的 WW 噸燃油是否足夠。判定問題的時間複雜度為 O(n) O ( n ) 。且對于單調增的 W W ，必然會存在一個值作為能否完成旅程的分界線。（單調性，滿足二分條件）

是以我們可以二分這個 WW，對每個确定的 W W 判定是否可以完成旅途。當二分的間距小于精度時，輸出這個 WW。

代碼

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

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

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

bool ok(double w) {
    double tot = m + w;
    for (int i = ; i < n; ++i) {
        tot -= tot / a[i];  // 起飛
        if (tot < m && fabs(tot - m) > EPS) return false;
        int d = (i + ) % 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) / ;
    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(), std::cout.tie();

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

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

    return ;
}