二分查找之-小车问题

作者:admin|日期:2019-02-11|热度:

题目描述


甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车,可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样,且小于车的速度。问:怎样利用小车才能使两人尽快同时到达。
原题链接:https://www.luogu.org/problemnew/show/P1258

解题思路:


如下图,分别计算A和B所用的时间,用二分查找确定X(A坐车的距离),使两人时间相等,输出时间。
二分查找之-小车问题

参考代码:


#include <bits/stdc++.h>
using namespace std;
double s,a,b;

double judge(double x){
double at,bt;
at=x/b+(s-x)/a;
bt=x/b+(x-x*a/b)/(a+b)*2+(s-x)/b;
return at-bt;
}
double findx(double left,double right){
double mid=(left+right)/2;
if(right-left<1e-10) return left;
double ans=judge(mid);
if(abs(ans)<1e-10) return mid;
if(ans>0) return findx(mid,right);
else return findx(left,mid);
}
int main(){
double x,t;
cin>>s>>a>>b;
x=findx(0,s);
t=(s-x)/a+x/b;
printf("%.6f",t);
return 0;
}