xdm,一道大厂前端算法题求最佳解答

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 199 天前的主题，其中的信息可能已经有所发展或是发生改变。

8 辆车，从同一个起点出发，全部油量都是满的，一车满油可以跑 100km ，车上只可以放一个油桶，中途任意时间、地点的一个车的油可以分给另外一个车，如何最终让一辆车跑最长距离，最长距离是？

有 xdm 知道咋解吗？最优解哦，谢谢

xdm

油量

距离

算法

2 条回复

rqzrqh

199 天前

思路：每一个阶段，其中一辆车始终给其他车以及自己供油，可以看作是其他车油都是满的，这个阶段结束这辆车被淘汰。

第一次是 8 辆车一起跑，到某个位置时，可以把其中一辆车剩下的所有油给其他 7 辆车。这次跑了 1/8*100km
第二次是 7 辆车一起跑，到某个位置时，可以把其中一辆车剩下的所有油给其他 6 辆车。这次跑了 1/7*100km
...
最后一次是 2 辆车一起跑，到某个位置时，可以把其中一辆车剩下的所有油给其他 1 辆车。这次跑了 1/2*100km
剩下 1 辆车跑 100KM 。
加起来是(1+1/2+...+1/8)*100KM

Yokin

199 天前

@rqzrqh 谢谢