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小于某一误差值。
上一篇: 摘要】面试中常见的智力问题