As Fast As Possible

As Fast As Possible

On vacationsn pupils decided to go on excursion and gather all together. They need to overcome the path with the lengthl meters. Each of the pupils will go with the speed equal tov₁. To get to the excursion quickly, it was decided to rent a bus, which has seats fork people (it means that it can't fit more thank people at the same time) and the speed equal tov₂. In order to avoid seasick, each of the pupils want to get into the busno more than once.

Determine the minimum time required for alln pupils to reach the place of excursion. Consider that the embarkation and disembarkation of passengers, as well as the reversal of the bus, take place immediately and this time can be neglected.
Input
The first line of the input contains five positive integersn,l,v₁,v₂andk (1 ≤ n ≤ 10 000,1 ≤ l ≤ 10⁹,1 ≤ v₁< v₂≤ 10⁹,1 ≤ k ≤ n) — the number of pupils, the distance from meeting to the place of excursion, the speed of each pupil, the speed of bus and the number of seats in the bus.
Output
Print the real number — the minimum time in which all pupils can reach the place of excursion. Your answer will be considered correct if its absolute or relative error won't exceed10^{- 6}.
ExamplesInput

5 10 1 2 5

Output

5.0000000000

Input

3 6 1 2 1

Output

4.7142857143

Note
In the first sample we should immediately put all five pupils to the bus. The speed of the bus equals2 and the distance is equal to10, so the pupils will reach the place of excursion in time10 / 2 = 5.

分析：参考自http://blog.csdn.net/libin66/article/details/52004623

首先最优情况下应有每个人坐公交时间和走路时间都相等（保证同时到达）。

这些人可以分为cnt=（n-k+1）/k部分；

设每个人坐bus路程L1，第二波人遇见bus时时间为T，则有（V1+V2）*T=2L1;

那么第二波人走了d=TV1=2L1V1/(V1+V2);

以后每一波人坐bus前都会继续多走d的路程，那么最后一波人走的路程（cnt-1）*d=L-L1；

（保证坐bus恰好到达终点）

则解得L1=L(V1+V2)/(2cnt*V1-V1+V2),总时间t=L1/V2+(L-L1)/V1;

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <ext/rope>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define vi vector<int>
#define pii pair<int,int>
#define mod 1000000007
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
const int maxn=1e3+10;
const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
using namespace std;
using namespace __gnu_cxx;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,l,v1,v2,k;
int main()
{
    int i,j,t;
    cin>>n>>l>>v1>>v2>>k;
    int cnt=(n+k-1)/k;
    double bus_path=1.0*l*(v1+v2)/(2*cnt*v1-v1+v2);
    double ans=bus_path/v2+(l-bus_path)/v1;
    printf("%.10f\n",ans);
    //system ("pause");
    return 0;
}

补二分做法：二分结束时间，然后根据方法一算出最后一组在期望时间能够走的总路程，与目标路程比较；

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,l,v1,v2;
int main()
{
    int i,j,k,t;
    cin>>n>>l>>v1>>v2>>k;
    int cnt=(n+k-1)/k;
    double tl=0,tr=(double)l/v1;
    while(tr-tl>1e-7)
    {
        double mid=(tl+tr)/2;
        double l1=(mid-(double)l/v1)*v1*v2/(v1-v2),p=(cnt-1)*2*l1/(v1+v2)*v1+l1;
        if(p<=l)tr=mid;
        else tl=mid;
    }
    printf("%.10f\n",tl);
    //system("pause");
    return 0;
}

原文链接: https://www.cnblogs.com/dyzll/p/5700981.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍