codeforces round #364 div2 D As Fast As Possible 二分+贪心

时间:2022-12-30 09:57:59
/*
   题目描述:有n个孩子,他们到终点的距离是l,他们步行的速度是v1;有一辆公交车,速度是v2,每次可以带k个孩子,
           初始时公交车和孩子们都在起点,现要求调整公交车的行程,使得所有孩子被送到终点时的时间最短。
                
    思路:问题的关键在于每一次公交车开往终点时,在哪里把运载的孩子放下然后返回。
        使用二分法,每次二分出一个所用的最小时间t,假设每次公交车从终点返回遇到步行的孩子们的时刻是cur,那么
        应当把这批孩子送到某个位置,使得这批孩子走到终点时的时刻恰恰是t,那么这批孩子乘车的时间怎么求呢?
        设他们乘车的时间是t0,那么有(l - v1 * cur - v2 * t0)/ v1 = t - cur - t0,等式左端是孩子下车走到终点还需要的时间,
        右端是下车时刻距离t时刻剩余的时间,解得t0 = (l - v1* t) / (v2 - v1),也就是每次司机接到孩子之后开t0时间就把
        他们放下
*/
#pragma warning(disable:4786)
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<string>
#include<sstream>
#define LL long long
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps=1e-6;
int time ;
int n , k ;
double v1 , v2 , l ;
bool ok(double t)
{
    double t0 = (l - v1 * t) / (v2 - v1) ;
    double cur = 0 ;
    for(int i = 1 ; i < time  ; i++){
        double rest = l - cur * v1 ;                //rest是孩子们上车时距终点的距离
        if(v2 * t0 > rest)      return false ;              //如果t0时间后孩子们已经过了终点,不成立
        cur += t0 + (v2 * t0 - v1 * t0) / (v2 + v1) ;       
        if(cur > t)     return false;               //如果司机接到某一批孩子的时间已经超过了t,不成立
    }
    double rest = l- cur * v1 ;
    if(rest / v2 <= t - cur)    return true;        
    else                              return false ;    //最后一批孩子直接用车送到终点,判断一下送到终点的时间与剩下时间的长短比较
}
double bsearch(double left , double right)
{
    double mid , ret = -1 ;
    for(int i = 0 ; i< 100 ; i++){
        mid = left + (right - left) / 2 ;
        if(ok(mid)){
            ret = mid ;
            right = mid  ;
        }
        else{
            left = mid ;
        }
    }
    return ret ;
}
int main()
{
    scanf("%d %lf %lf %lf %d",&n , &l , &v1 , &v2 , &k ) ;
    time = n % k == 0? n / k : n / k + 1 ;
    double ans = bsearch(0 , l ) ;
    printf("%.8lf\n",ans);
    return 0;
}