首页 > > 程序设计 > C/C++ >

codeforces 700A As Fast As Possible 二分求和…

2018-06-17 23:32:25来源：未知阅读 ()

分析：一辆车最多载k个人，车的速度肯定比人快，所以想要到达时间最短，那么每个人必须做一次公交车。那么把n个人分成p=(n+k-1)/k组。设最短时间为t，每人乘车时间为t1，则t1*v2+(t-t1)*v1=L。设每次车子返回走的时间为t2，则(t1+t2)*v1+t2*v2=t1*v2。由这两个式子可以写出t1,t2的表达式。又因为p*t1+(p-1)*t2=t. 所以可以以最短时间L/v2为左端值，以L/v1为右端值二分t。　　

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n,k;
double l,v1,v2;
int solve(double t,int p)
{
    double t1=(l-t*v1)/(v2-v1);
    double t2=(v2-v1)*t1/(v1+v2);
    double ans=t1*p+t2*(p-1);
    if(ans<t) return 1;
    return 0;
}
int main()
{
    scanf("%d%lf%lf%lf%d",&n,&l,&v1,&v2,&k);
    int p=(n+k-1)/k;
    double low=l/v2,high=l/v1;
    double mid=(low+high)/2;
    while(high-low>0.000001)
    {
        int ret=solve(mid,p);
        if(ret==1)
            high=mid;
        else
            low=mid;
        mid=(low+high)/2;//这个地方竟然坑了我一把，如果把这一行放置while循环的第一个语句，结果wa了。。。
    }
    printf("%.10lf\n",mid);
    return 0;
}

但是，为什么要用二分呢，就是因为cf上面有二分这个标签嘛？明摆着t=p*t1+(p-1)*t2. 所以可以直接求解啊！

#include <cstdio>
#include <cstring>

int main()
{
    int n,k;
    double v1,v2,l;
    scanf("%d%lf%lf%lf%d",&n,&l,&v1,&v2,&k);
    int p=(n+k-1)/k;
    double a=l*p/(v2-v1)+l*(p-1)/(v1+v2);
    double b=v1*p/(v2-v1)+v1*(p-1)/(v1+v2)+1;
    printf("%.10lf\n",a/b);
    return 0;
}