学步园

有一个环形公路上有n个加油站，第i个加油站的油量为a_i。假设有一辆邮箱体积无穷大的汽车，初始邮箱是空的，汽车从加油站i行驶到加油站i+1需耗油g[i]。

问是否能够选出某个加油站作为起点，使汽车能够绕环形公路行驶一圈返回到该加油站。

实现函数int selectGasStation(int a[], int g[], int n)，如果存在满足条件的加油站，返回该加油站的序号(0-based)。否则返回-1。

提示：n可能达到10⁶，O(n²)的枚举算法会超出时间限制

据说是google在08年的一道题，哎，好难啊，在面试时那么几分钟我肯定想不出来的，哎。

主要就是变形成为查找是否有一个n长的前缀和全大于0的序列。

#include <vector>
using namespace std;

int selectGasStation(const vector<int> &a, const vector<int> &g) {
	vector<int> line(a.size()<<1);

	int n=line.size();
	for(int i=0;i<n;i++)
		line[i]=a[i%a.size()]-g[i%a.size()];

	int start=0;
	int oil=0;
	for(int i=0;i<n;i++)
	{
		if ( oil<0 )
		{
			start=i;
			oil=line[i];
		}
		else
		{
			oil+=line[i];	
			if ( i-start>=a.size() )
				return start;
		}
	}
	return -1;
}