加油站-汽车问题

给定两个数列 P 和 D。P[i] 代表第 i 个加油站的油量，D[i] 代表从当前加油站到下一个加油站的距离。汽车每走单位距离，就会消耗单位油量。注意：加油站是环形单链表状的分布，也就是说，从当前加油站只能沿着一条仅有的路去向下一个加油站。求一个起始加油站，从这个加油站出发，可以遍历所有加油站。

思路：通过 arr[i] = D[i] - P[i] 得到一个新的数组。用Kadane算法找出最大子数组，这个最大子数组的起点就是所求的起始加油站。

注意：这里的子数组可以跨过数组尾部，并和数组前部相接。

思路二:

那么这题包含两个问题：
1. 能否在环上绕一圈？
2. 如果能，这个起点在哪里？
第一个问题，很简单，我对diff数组做个加和就好了，leftGas = ∑diff[i]，如果最后leftGas是正值，那么肯定存在这么一个起始点。如果是负值，那说明，油的损耗大于油的供给，不可能有解。得到第一个问题的答案只需要O(n)。
对于第二个问题，起点在哪里？
假设，我们从环上取一个区间[i, j], j>i，然后对于这个区间的diff加和，定义
sum[i,j] = ∑diff[k] where i<=k<j
如果sum[i,j]小于0，那么这个起点肯定不会在[i,j]这个区间里，跟第一个问题的原理一样。举个例子，假设i是[0,n]的解，那么我们知道任意sum[k,i-1] (0<=k<i-1) 肯定是小于0的，否则解就应该是k。同理，sum[i,n]一定是大于0的，否则，解就不应该是i，而是i和n之间的某个点。所以第二题的答案，其实就是在0到n之间，找到第一个连续子序列（这个子序列的结尾必然是n）大于0的。
至此，两个问题都可以在一个循环中解决。

代码:

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
	vector<int> diff(gas.size());
	for(int i =0; i< gas.size(); ++i)
	{
		diff[i] = gas[i] - cost[i];
	}
	  
	int leftGas=0, sum =0, startnode=0;
	for(int i =0; i<gas.size(); ++i)
	{
 		leftGas += diff[i];
		sum += diff[i];
		if(sum <0) //只要小于0就不可能是解
		{
			startnode = i+1;
			sum=0;
		}
	}
	if(leftGas <0)
		return -1;
	else
		return startnode;

}

秒客网

加油站-汽车问题

相关文章