欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

D - 手推车问题(二分法) - 解决方案:

最编程 2024-05-03 21:24:25
...

法一:(数学分析)

因为甲乙到终点的时间相同并且要求最短,则二人走和坐车的时间相等,即走和坐车的路程相同,并且车只回去接一次。

|--x----|----s-2*x-----|---x----|

设人走的路程为x,时间为t1,坐车路程为s-x,时间为t2,车回去接人的时间为t3,总共耗时为t。

人走的时间=车回去接另一个人的时间+另一个人坐车的时间。即t1=t2+t3,即x/a=(s-2*x)/b+(s-x)/b,得x=2*a*s/(3*a+b),时间为x/a+(s-x)/b。

法二:二分

t1为车载甲到甲下车的时间,t2为车返回去接乙的时间,t1+t2时间内乙一直在步行

m(甲用的时间),n(乙用的时间)

m<n的话,不公平啦~,说明甲坐车的时间长(快),mid(甲下车的地方)应该小一点,故r=mid

反之,l=mid;直到r-l小于某一误差值。