在圆圈中找到索引,以便旅行者可以完成一轮

Question

我出现在一次采访中.我陷入了一个问题.我问的是同样的问题.

问题: 给出了循环道路.那条路上有许多汽油泵.每个汽油泵都给出了一定量的汽油.还给出了每两个连续汽油泵之间的距离.现在有一辆车具有无限容量的空油箱.构建一个算法,以便车辆可以覆盖整个圆形而无需任何回溯.这样的道路绝对是可能的.

输入: (int fuel [],int distance [])

输出:汽油泵指数从车辆可以完成圆形的圆形道路.

我的方法:

1. 检查每个汽油泵,如果油箱在路径之间是空的,则移动到下一个汽油泵.并再次开始相同的过程.该算法需要O(N ^ 2),这里N =汽油泵的数量.

2. 然后我转到二进制搜索概念,将复杂度降低到O(n*logn).但我没有完成解决方案.我搞砸了这个解决方案.

3. 然后我尝试应用一些智能,选择那两个汽油泵之间的左汽油最大的汽油泵.

Answer 1

(这可能相当于Evgeny Kluev发布的算法,我不明白.如果是这样,那个答案有优先权.)

让F_i_j成为罐中燃料的净燃料,在到达j时已经开始于i,燃料箱中的燃料为零,然后填充在i处.

通过围绕在每个节点处添加燃料的圆并且减去每个边的燃料成本来计算每个节点i的F_0_i.

如果F_0_0,从0开始的电路末端的净燃料是负的,则系统中没有足够的燃料(根据问题陈述,这不应该发生).

如果没有F_0_i为负数,则报告0作为结果.

否则,找到具有最大负值F_0_s的节点s.选择s作为起始节点.

对于任何节点i,F_s_i等于F_0_i + abs(F_0_s).由于F_0_s是最负的F_0_i,这使得F_s_i非负.

Worked example, as suggested in a comment by Handcraftsman:
Label nodes 0 through 4

node: 0,1,2,3,4
fuel: 1,3,4,4,1
dist: 1,4,2,2,2


First calculate F_0_i for i = 1, 2, 3, 4, 0
Start at node 0 with 0 fuel.

f_0_1 = 0 + 1 - 1 = 0, min score 0, node 1;
f_0_2 = 0 + 3 - 4 = -1, min score -1, node 2;
f_0_3 = -1 + 4 - 2 = 1;
f_0_4 = 1 + 4 - 2 = 3;
f_0_0 = 3 + 1 - 2 = 2;

f_0_0 is non-negative, so there is enough fuel.

The minimum score was -1, at node 2, so the result is node 2.