codeforces 1010A（二分答案）

题意描述

火箭自身的重量为m，每次从第i个星球起飞的系数为a[i]，从第i个星球降落的系数为b[i]，飞行路线为1起飞-2降落-2起飞-3降落-n降落-n起飞-1降落，如果火箭携带的燃料重量为x，则每次起飞降落花费的燃料为(x+m)/系数。询问可以使火箭完成飞行路线所需要的最少重量的燃料，如果不能完成，则输出-1

思路

这道题很明显是二分答案，check函数需要判断的是x+m吨的燃料最后结束飞行后剩余的重量是否大于m，最后二分结束后还需要再判断一下二分后的答案是否符合条件，如果不符合就输出-1。这道题还有一个坑点就是二分所取得eps为2e-7，否则会超时

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=2020;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int a[N],b[N];
int n;
double m;
bool check(double res){
    double sum=res+m;
    for(int i=0;i<n-1;i++){
        sum-=(sum/a[i]);
        sum-=(sum/b[i+1]);
    }
    sum-=(sum/a[n-1]);
    sum-=(sum/b[0]);
    return sum>=m;
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    double l=0,r=1000000000;
    double eps=2e-7;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    double res=l;
    for(int i=0;i<n-1;i++){
        res-=(res/a[i]);
        res-=(res/b[i+1]);
    }
    res-=(res/a[n-1]);
    res-=(res/b[0]);
    if(res>0) printf("%.10f\n",l);
    else printf("-1\n");
}
int main(){
    //IOS;
    solve();
    return 0;
}

本文地址：https://blog.csdn.net/weixin_45729946/article/details/107387918