题目:两个逃犯从A地逃跑到B地,出发时A地有一辆可带一人的自动驾驶车。又知道两人步行速度相同。问怎样利用小车才能让两人尽快同时到达B地?
输入文件为escape.in,有三个int类型整数,分别表示A、B两地距离,步行速度和车速。
输出文件为escape.out,有一个小数位数为2的浮点数,也就是最短时间。
分析:如同,设两个人分别为甲、乙,则最优方案为甲先乘车到C后下车步行,小车回头接已经走到E的乙,假设在D相遇,乙乘车到达B时正好甲也步行到达,这样花费的时间最小。
那就是求C点的位置了。设A、B距离为S,步行速度为a,车速为b,甲耗时T1,乙耗时T2.
在设C0为起始点,C1为终点,取中点位置C=(C0+C1)/2作为测试点,即计算甲耗时T1与乙耗时T2,若T1<T2,则取C与C0的中点,否则取C与C1中点。如此反复循环直到T1=T2即可。
代码如下:
#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
freopen("escape.in", "r", stdin);
freopen("escape.out", "w", stdout);
float s, a, b, c, c0, c1, t1, t2, t3, t4;
c0 = 0;
c1 = s;
do
{
c = (c0 + c1) / 2;
t3 = c / b; //甲乘车到C的时间
t1 = t3 + (s - c) / a; //甲用的总时间
t4 = (c - t3 * a) / (a + b); //小车从C回头与乙相遇的时间
t2 = t4 + t3 + (s - (t3 + t4)*a) / b;//乙用的总时间
if (t1 > t2)
c0 = c;
else
c1 = c;
} while (fabs(t1 - t2) > 1e-4);
printf("%4.2f", t1);
return 0;
}