做出完整的圆形路径,最短路径运动？

Question

我在接受采访时得到了这个问题,但我无法解决.

你有一条环形公路,有N个加油站.你知道每个车站有多少气体.你知道从一个站到下一个站所需的气体量.你的车从0气开始.问题是:创建一个算法,知道你必须从哪个加油站开始驾驶以完成圆形路径.它没有指定您必须访问所有站.你只能顺时针驾驶.

我不得不在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的回答,作为决定从哪里开始的改进,折扣站没有足够的气体到达下一站并按照燃气量(下降)的顺序通过起始站.

请注意,这假设我们访问所有加油站.如果您需要最佳解决方案,则需要改进跳过加油站(问题没有说明这一点).