Codeforces Round #364 (Div. 2) D. As Fast As Possible(binary search)

题目链接
大意:n个人,要走l长的路,有辆车可以带k个人。
人带速度 v 1 v_1 v1,车的速度 v 2 v_2 v2
让你求出最短通过时间
显然时间是具有单调性的,我们二分答案来check。
每次用车装k个人往后走(check的值的剩余时间)一个最长的距离 x 1 x_1 x1, x 1 x_1 x1表示车能走的最大距离, x 2 x_2 x2人还要走的距离, t o t tot tot已经花的时间
x 1 v 2 + x 2 v 1 = m i d t o t \frac{x_1}{v_2}+\frac{x_2}{v_1}=mid-tot v2x1+v1x2=midtot
剩下的人同时往后,然后车再返回接人。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,k;
double l,v1,v2;
const double eps=1e-8;
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>l>>v1>>v2>>k;
    double L=0,r=l,ans=L;
    cout<<fixed<<setprecision(18);
    int g=0;
    while(++g<200){
        double mid=(L+r)/2;
        double len=l;
        int now=n;
        double res=0;
        while(now>0){
            double x2=(mid-res)*v1*v2-len*v1;
            x2/=v2-v1;
            double x1=len-x2;
            len-=x1/v2*v1;
            res+=x1/v2;
            now-=k;
            if(now<=0)break;
            double t3=len-x2;
            t3/=(v1+v2);
            len-=t3*v1;
            res+=t3;
        }
       // cout<<mid<<' '<<res<<endl;
        if(res<=mid)ans=mid,r=mid;
        else L=mid;
    }
    cout<<ans<<endl;
    return 0;
}
全部评论

相关推荐

牛客771574427号:恭喜你,华杰
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务