逃亡之美

题目:两个逃犯从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;
}

 

上一篇:cookie 注入(搬运)


下一篇:Kubernetes基础:查看状态、管理服务