5

我出现在采访中。我陷入了一个问题。我也在问同样的问题。

问题： 给出了环形路。那条路有许多加油泵。每个汽油泵都有一定量的汽油。还给出了每两个连续汽油泵之间的距离。现在有一种车辆具有无限容量的空油箱。建立一个算法，使车辆可以覆盖整个回合而无需任何回溯。假设这样的路径绝对是可能的。

输入： （int燃料[]，int距离[]）

输出：车辆可以绕完一圈环形道路的汽油泵指数。

我的方法：

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

  2. 然后我转向二进制搜索概念，以将复杂性降低到 O(n*logn)。但我未能得出解决方案。我在这个解决方案中搞砸了。

  3. 然后我尝试应用一些智能，通过选择在两个汽油泵之间剩余汽油最大的汽油泵。

4

5 回答 5

8

（这可能相当于 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.
于 2012-11-07T05:24:54.307 回答
3

蛮力解决方案应该是显而易见的。从每个 i 开始，检查每个点是否可以通过可用的气体到达。返回第一个 i ，您可以为其完成行程而不会达到负数。然而，这种方法将是二次的。让我们看看如何改进。

我们可以在这里采取贪婪的方法。

1 如果 gas 的总和大于 cost 的总和，则意味着不会有任何解决方案。我们可以丢弃我们开始的点

2 假设您从 i 开始，并在 j 处达到 sum(gas) - sum(cost) 的第一个负数。我们知道 TotalSum(gas) - TotalSum(cost) > 0。所以我们可以将 i 丢弃到 j 并从 j + 1 开始。

上述算法的Java代码 

        public int canCompleteCircuit(final List<Integer> gas, final List<Integer> cost) {
            int start = 0;
            int totalGas = 0;
            int totalCost = 0;
            int currentCost = 0;
            for (int i = 0; i < gas.size(); i++) {
                totalCost += cost.get(i);
                totalGas += gas.get(i);
                currentCost += gas.get(i) - cost.get(i);
                if (currentCost <0){
                    start = i + 1;
                    currentCost = 0;
                }
            }

            if (totalCost > totalGas){
                return -1;
            }

            return start;

        }
于 2015-12-19T16:13:17.400 回答
2

如果可以找到正确的课程，我必须先了解才能解决问题。

D- 所有距离的 P总和 - 所有燃油泵的总和

  1. 如果P < D问题无法解决
  2. 如果P = D它总是有解决方案，请在下面证明
  3. 如果P > D我们可以减少一些泵并像应用溶液一样P = D。

因此，我们假设P = D，即我们拥有完成课程所需的确切燃料量。让我们画一张图表，油箱中的燃料量作为时间的函数。如果tanking time 等于0，它不是一个真正的函数，但它并不重要。我们从任何地方开始，油箱里有一些燃料。

泵 1、4、3 和距离 2、5、1 的示例：

   |\       
   | \      
|\ |  \  |\ 
  \|   \ |  
        \|

注意事项：

  1. 我们可能会无限地四处走动，图表也会以同样的方式重复。我们将以与开始时相同的燃料量回到起点。
  2. 总会有一个油量最低的点，并且总是同一个站点（如果有几个最小站点，它不会改变任何东西）
  3. 如果我们从不同的地方开始，最小的点总是落在同一个站。

基于上述，我们从一个最小的泵开始并为其分配 0 级。这就是我们的燃料永远不会低于 0 的证据，也就是说，我们将能够继续绕着绕绕…

现在我们看到Evgeny 的解决方案是正确的，尽管S和的计算S/N是不必要的。我们只需要加上泵值并减去距离，在 Evgeny 的算法中是V。因此，最佳出发站是我们到达时燃料含量最少的站。

我花了很多时间才明白为什么 Evgeny 会从任意方向开始。为什么他确定解决方案存在于他所采取的方向而不是相反的方向？但是当我们知道这P = D是完成课程的充分条件时，我们也知道方向并不重要。我们应该选择一个不同的车站作为相反方向的起点，但我们可以在两个方向上都这样做。

Nithis，给了你多少时间？能说一下公司名字吗？:) 我认为这是一项相当艰巨的任务，至少对于一个不熟悉类似循环问题的人来说。

于 2012-11-07T06:52:34.333 回答
0

这是递归的条件。首先，您检查最后一段是否还有燃料。如果需要的燃料是 x 并且泵 n 中的燃料是 y。如果 x>y 那么我们需要 (xy)+泵 n,n-1 之间的伸展所需的燃料，否则只有最后一个所需的燃料但是泵 n-1 需要拉伸。这会一直持续到到达泵 1。

于 2012-11-07T05:11:58.723 回答
0 
 public static void main(String[] args) {

  int petrol[] = { 1, 3, 4, 4, 1 };
  int distance[] = { 1, 4, 2, 2, 2 };

  petrol = new int[] { 4, 6, 7, 4 };
  distance = new int[] { 6, 5, 3, 5 };
  List<PetrolPump> petrolPumps = PetrolPump.getAll(petrol, distance);

  int start = 0;
  int end = petrol.length;

  int remainingPetrol = 0;

  do {
     remainingPetrol += petrolPumps.get(start).petrol - petrolPumps.get(start).distance;

     if (remainingPetrol < 0) {
        remainingPetrol = 0;
        end = start;
     }

     start++;
     if (start >= petrol.length) {
        start = 0;
     }
  } while (start != end);

  System.out.println(end + 1);

}

static class PetrolPump {
  int petrol;
  int distance;

  PetrolPump(int petrol, int distance) {
     this.petrol = petrol;
     this.distance = distance;
  }

  static List<PetrolPump> getAll(int[] petrol, int[] distance) {
     List<PetrolPump> petrolPumps = new ArrayList<PetrolPump>(distance.length);

     for (int i = 0; i < distance.length; i++) {
        petrolPumps.add(new PetrolPump(petrol[i], distance[i]));
     }

     return petrolPumps;
  }
}
于 2016-03-02T02:41:28.580 回答