#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*問題:There are N gas stations along a circular route, where the amount of gas at station i is gas[i].You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.Note:The solution is guaranteed to be unique.分析:這是環(huán)形的部分。可以直接求出diff[i]=gas[i] - cost[i]，這就是第i棧可以實(shí)際獲得的的油量。可以先求出diff數(shù)組，將數(shù)組全部累加求和，如果和<0，肯定不可以diff數(shù)組和>=0，肯定可以，題目說了解只有唯一一個(gè)，那么唯一的解會(huì)有什么特點(diǎn)？必須從diff[i]中為正值的地方開始行使，如果存在多個(gè)正值的地方，最簡單的方式就是遍歷所有diff數(shù)組中為正值的地方。但是這樣時(shí)間復(fù)雜度就是O(n^2)了。舉例:gas: 5 3 6 1(補(bǔ)充的汽油量)cost:3 4 3 5(每一站消耗的汽油量)diff:2 -1 3 -4diff每個(gè)元素和該元素相鄰的前一個(gè)的元素累加求和記為數(shù)組sumsum: 2 1 4 0,發(fā)現(xiàn)了就是累加求和后值最小的元素的下一個(gè)元素sum的真實(shí)意義是從第0個(gè)車站開始后，開到當(dāng)前站依次剩余的汽油量。找到一個(gè)最小值sum[k]，表示到達(dá)第k站剩余的汽油量最少，也就是從第0個(gè)站到達(dá)第k個(gè)站累計(jì)消耗的汽油最多，那么從第k+1個(gè)站到第0個(gè)站消耗的汽油量最少，顯然應(yīng)該從第k+1個(gè)站開始。證明假設(shè)不從第k+1個(gè)站開始，比如從第j(j!=k+1)個(gè)站開始出發(fā)，如果選擇從第k+1個(gè)站開始，可以成功輸入:4(元素個(gè)數(shù))5 3 6 1(補(bǔ)充的汽油量)3 4 3 5(每一站消耗的汽油量)45 3 6 13 4 3 645 3 6 44 5 7 121 22 1輸出:0-131關(guān)鍵:1 diff每個(gè)元素和該元素相鄰的前一個(gè)的元素累加求和記為數(shù)組sumsum: 2 1 4 0,發(fā)現(xiàn)了就是累加求和后值最小的元素的下一個(gè)元素sum的真實(shí)意義是從第0個(gè)車站開始后，開到當(dāng)前站依次剩余的汽油量。找到一個(gè)最小值sum[k]，表示到達(dá)第k站剩余的汽油量最少，也就是從第0個(gè)站到達(dá)第k個(gè)站累計(jì)消耗的汽油最多，那么從第k+1個(gè)站到第0個(gè)站消耗的汽油量最少，顯然應(yīng)該從第k+1個(gè)站開始。*/class Solution {public:    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {		if(gas.empty() || cost.empty() || gas.size() != cost.size())		{			return -1;		}		int size = gas.size();        vector<int> diff(size , 0);		int total = 0;		for(int i = 0 ; i < size ; i++)		{			diff.at(i) = gas.at(i) - cost.at(i);			total += diff.at(i);		}		//總的汽油剩余量為0，肯定不可能		if(total < 0)		{			return -1;		}		int minSum = diff.at(0);//最小值從第一個(gè)元素開始		int minIndex = 0;		int tempSum = diff.at(0);		for(int i = 1 ; i < size ; i++)		{			tempSum = diff.at(i) + tempSum;//計(jì)算開到第i個(gè)站時(shí)，累計(jì)剩余的汽油量			if(tempSum < minSum)//計(jì)算累計(jì)剩余汽油量最少的站			{				minSum = tempSum;				minIndex = i;			}		}		//因?yàn)橹挥幸粋€(gè)解，出發(fā)的棧必定是從累計(jì)剩余汽油量最少的站的下一個(gè)站出發(fā)		if(minIndex == size - 1)		{			return 0;		}		else		{			return (minIndex + 1);		}    }};void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> gas;	 vector<int> cost;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 gas.clear();		 cost.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 gas.push_back(value);		 }		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 cost.push_back(value);		 }		 int index = solution.canCompleteCircuit(gas , cost);		 cout << index << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}