Gas Station(Medium)

1.在做pat的to fill or not to fill的时候想起同样是加油站的题目，于是翻出来复习一下

2.关键在于理解潜在的条件。假设油量为tank，如果到了当前站i，tank<0，即不能到达站i+1，那么起始站start和i之间的任何一个站i都不能到达站i+1。因为每个站至少贡献了0或者>0的油量，去掉一个站，那么tank必然比现在的油量还要小，所以更加不可能达到i+1.

证明：

设tank[a,b]是指以a为起始站，到达b站后，油箱的油量。

如果上述2结论不成立，则可以推导出，在start与i之间的某一个站j，使得tank[j,i]>tank[start,i]，又tank[start,i]=tank[start,j]+tank[j,i]，那么推得tank[start,j]<0，

而车能够从start走到i，所以对于任意k属于[start,i]，均有tank[start,k]>=0，与tank[start,j]<0矛盾，所以2结论是正确的。

AC代码：

class Solution {

public:

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int tank=0;//当前的油箱油量

        int start=0;//从第0个站开始计算，后面也作为结果进行返回

        int n=gas.size();

        for(int i=0;i<gas.size();i++)

        {//遍历所有加油站

            tank+=gas[(i+start)%n]-cost[(i+start)%n];//更新油箱的油量

            if(tank<0)

            {//如果tank小于0，表明没办法从i走到下一个油站,那么start直接从下一站开始

            //如果无法从start达到i，那么start和i之间任何一个站都不能达到i，因为每个站至少贡献了0和>=0的油量

                start=i+start+1;//start从当前i站的下一个站开始

                i=-1;//使得下次从i=0开始

                if(start>=n)

                {//已经把所有情况都遍历了，仍不能满足要求

                    return -1;

                }

                tank=0;

            }

        }

        return start;

    }

};

之前的AC代码：

class Solution {

public:

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int tank=0;

		int start=0;

		int n=gas.size();

		for(int i=0;i<n+start;i++)

		{

			tank=tank+gas[i%n]-cost[i%n];

			if(tank<0)

			{//如果油箱汽油小于0，则不能到达，即从start无法到达i，start与i之间的任何一站都不可能达到i

			 //因为从start到i这个过程中，每一站至少贡献0的油量，假设去掉start，则tank会减去0或者一个正数，导致更加不可能到达i

				start=i+1;//从下一个站继续开始重新计算

				if(start>=n)//如果下一个站已经超过了n，证明前n个站都不可能完成循环，所以return-1

				    return -1;

				tank=0;

			}

		}

		return start;//如果循环结束后tank大于等于0，则能够达到目的地

    }

};

巴特西

Gas Station(Medium)

最新文章

热门文章