做全圆路径，最短路径练习

class GasStation
  int gasAtStation;
  int gasToMoveToNextStationNeeded;
  string nameOfGasStation;

GasTation wheretoStart(List<GasStation> list)
{
}

static void Main(string[] args)
        {
            int[] gasOnStation = {1, 2, 0, 4};
            int[] gasDrivingCostTonNextStation = {1, 1,2, 1};
            FindStartingPoint(gasOnStation, gasDrivingCostTonNextStation);
        }
        static void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts)
        {
            // Assume gasOnStation.length == gasDrivingCosts.length
            int n = gasOnStation.Length;
            int[] gasEndValues = new int[n];
            int gasValue = 0;
            for (int i = 0; i < n; i++)
            {
                gasEndValues[i] = gasValue;
                gasValue += gasOnStation[i];
                gasValue -= gasDrivingCosts[i];
            }
            if (gasValue < 0)
            {
                Console.WriteLine("Instance does not have a solution");
                Console.ReadLine();
            }
            else
            {
                // Find the minimum in gasEndValues:
                int minI = 0;
                int minEndValue = gasEndValues[0];
                for (int i = 1; i < n; i++)
                {
                    if (gasEndValues[i] < minEndValue)
                    {
                        minI = i;
                        minEndValue = gasEndValues[i];
                    }
                }
                Console.WriteLine("Start at station: " + minI);
                Console.ReadLine();
            }
        }

解决这个问题的一个简单方法是使用暴力破解方法。也就是说，尝试每一种可能性，排除那些行不通的。

。依次从每个加油站出发(对每个加油站重复下面的步骤)。

• 有一个变量来定义当前气体液位。
• 按顺时针顺序穿过每个加油站。
  1. 加满汽油(按加油站数量增加汽油量)。
  2. 检查您可以移动到下一站(gas >= gasToMoveToNextStationNeeded)
     • 如果没有，这不是一个解决方案，所以移动到下一个起始位置。
     • 如果是，减去使用的气体量，然后继续前进，直到再次到达起点。
  如果你回到起点加油站，你就有答案了。

---

编辑根据@Vash的回答，作为决定从哪里开始的改进，折扣没有足够的汽油的站自己到达下一个站，并按照汽油量(下降)的顺序通过起始站工作。

---

注意，这里假设我们访问了所有的加油站。如果你需要一个最优的解决方案，将需要改进跳过加油站(问题没有指定这个)。

这是@George Duckett回答的优化案例。

• 选择并记住你的出发站。
• 环路(1)顺时针通过站点。
  • 获取燃料。
  • 如果有足够的燃料，进入下一站，减少剩余燃料量，继续循环(1)

如果你到达了起跑站，问题就解决了。

如果你没有足够的燃料到达下一个站

• 记住你的终端站。
• Distance_to_start = 0, fuel_to_start = 0
• 从你的起跑站逆时针循环(2)。
  • 将可用燃料和到下一站的距离添加到您的计数器
  • 如果fuel_to_start> distance_to_start，你有一些多余的燃料。把这个站标记为你的新起点，然后再次转到循环(1)——也许你现在可以继续了。
  • 否则，继续循环(2)

如果你逆时针走到已经访问过的站点-运气不好，站点上没有足够的燃料可以走一圈。

任务确实是开放的。当你做一个循环，所以最好的选择是从站有最大的足够的燃料量开始。这意味着你可以给车加满油，然后开到最近的加油站。

当我们有地方开始时，我们只需要决定我们需要在哪个加油站停下来。在第一次运行中，我们可以在每一站停一站。

编辑。

与Lasse V. Karlsen讨论后提出的小改进。

如果选择的第一个站不能成功进行循环。然后以同样的方式选择下一个更小的*燃料/道路比例。

*小于第一选择站的比例。

制作车站循环表。求

为正值的任意站

多余= (gasAtStation - gasToMoveToNextStationNeeded)

这是当前基数。

当下一个站点有负超额值时，将它的gasAtStation和gasToMoveToNextStationNeeded添加到当前基础字段中，并从列表中删除此站点。

对所有阳性台站循环重复。

当没有多余的站点可以移除时:

如果列表中仍然有一个或几个非负站点，则其中任何一个都适合作为起点。

的例子:

A(-50) B(100) C(-20) D(-90) E(60) [C->B]

A(-50) B(80) D(-90) E(60) [D->B]

A(-50) B(-10) E(60) [A->E]

B(-10) E(10) [B->E]

E (0)

虽然尝试每个起跑站当然工作良好，但它需要二次时间，而有一个简单的线性时间算法。

使用一辆神奇的车，可以继续前进，如果燃料水平到负。从任意一个车站开始，做一次完整的旅行，参观每个车站。如果返回时燃料少于零，就没有解决方案。否则，最佳起点是到达时燃油最少的加油站。

这是有效的，因为所有可能的行程的燃料水平是相同的，除了一个恒定的偏移。

如果我们定义从a站到B站的行程包括GasAtStation a和TripCost。然后对于每一次旅行，我们得到TripBalance = GasAtStation-TripCost

所有行程平衡的总和必须大于或等于零，否则不存在解。该解决方案包括拥有一个包含每个加油站的旅行余额的列表，并迭代条目，为tripBalance保留一个变量，如果tripBalance变为负值，则旅行应该在下一个加油站开始，如果是，我们重置tripBalance并继续处理，直到检查列表中的最后一个条目:

public int FindFirstStation(List<int> tripBalances)
{
  if (tripBalances.Sum() < 0) return -1;
  var firstStation = 0;
  var tripBalance = 0;
  for (int i = 0; i < tripBalances.Count; i++)
  {
    tripBalance += tripBalances[i];
    if (tripBalance < 0)
    {
      tripBalance = 0;
      firstStation = i + 1; // next station
    }
  }
  return firstStation;
}

我用下面的代码测试它:

[TestMethod]
public void Example()
{
  var tripBalances = new List<int> { 0, 1, -2, 3 };
  var resolver = new GasStationResolver();
  var indexOfGasStation = resolver.FindFirstStation(tripBalances);
  Assert.AreEqual(3, indexOfGasStation);
}

请注意，传递的值是从问题头中给出的示例中计算出来的。在这种情况下，答案是我们列表中的最后一个加油站应该是第一个加油站。最后，如果没有解，该方法返回-1。

另一个例子，以覆盖加油站的高汽油不是解决方案:

/// <summary>
/// Station 1 - Gas: 3   Cost: 4
/// Station 2 - Gas: 10  Cost: 11
/// Station 3 - Gas: 8   Cost: 9
/// Station 4 - Gas: 6   Cost: 3
/// Station 5 - Gas: 4   Cost: 2
/// 
/// Then - Trip Balances are:
/// Station 1 - -1
/// Station 2 - -1
/// Station 3 - -1
/// Station 4 -  3
/// Station 5 -  2
/// </summary>
[TestMethod]    
public void SecondExample()
{
  var tripBalances = new List<int> { -1, -1, -1, 3, 2 };
  var resolver = new GasStationResolver();
  var indexOfGasStation = resolver.FindFirstStation(tripBalances);
  Assert.AreEqual(3, indexOfGasStation);
}

找到有最多汽油的加油站，但当加到下一站的汽油不超过油箱的容量时。

这也许?

• 查找汽油量最大的加油站
• 列出所有加油站，并取其燃油价值，减去在那里开车的成本
• 开车到值最高的加油站
• 重复，直到所有加油站被访问