我出现在采访中。我陷入了一个问题。我也是这么问的。
Question: There is circular road is given. That road contains number of petrol pumps. Each petrol pump have given amount of petrol. Distance between each two consecutive petrol pump is also given. Now there is a vehicle is given having empty fuel tank of limitless capacity. Build an algorithm so that vehicle can cover complete round without any backtracking. It is given that such path is definitely possible.
输入: (int fuel[], int distance[])
输出: 车辆可以绕完整圈环形道路的汽油泵索引。
我的方法:
从每个汽油泵检查，如果路径之间的油箱是空的，则移动到下一个汽油泵。并再次开始相同的过程。该算法需要 O(N^2)，这里 N = 汽油泵的数量。
然后我转向二分搜索概念，将复杂度降低到 O(n*logn)。但我未能得出解决方案。我搞砸了这个解决方案。
然后我尝试应用一些智能，选择两个加油泵之间左侧汽油最多的那个加油泵。
最佳答案
(这可能等同于 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.
关于algorithm - 找到圆圈中的索引，使旅行者可以完成一轮，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13258144/