c# - 做完整的循环路径，最短路径练习？

Question

我在面试中遇到了这个问题，但我无法解决。

You have a circular road, with N number of gas stations. You know the ammount of gas that each station has. You know the ammount of gas you need to GO from one station to the next one. Your car starts with 0 gas. The question is: Create an algorithm, to know from which gas station you must start driving to COMPLETE the circular PATH. It does not specify that you must visit all stations. You can only drive clockwise.

我必须用 C# 来做

我开始的唯一代码是使用 GasStation 实体

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();
            }
        }

谢谢

Answer 1

解决此问题的一种简单方法是使用蛮力法。即尝试每一种可能性并丢弃那些不起作用的。

即依次从每个加油站开始(对每个起始站重复以下操作)。

• 有一个定义当前气体水平的变量。
• 按顺时针顺序遍历每个加油站。
  1. 加满油(按加油站数量增加油量)。
  2. 检查您是否可以移动到下一站 (gas >= gasToMoveToNextStationNeeded)
     • 如果不是，则这不是解决方案，因此移动到下一个起始位置。
     • 如果是，减去所用的汽油量，然后继续前进，直到再次到达起点。
  3. 如果您回到出发的加油站，您就会得到答案。

---

编辑根据@Vash 的回答，作为在决定从哪里开始时的一种改进，本身没有足够汽油到达下一站的折扣站并按照起始站的顺序工作气体量(降序)。

---

请注意，这假设我们访问了所有加油站。如果您需要最佳解决方案(问题未指定)，则需要改进以跳过加油站。