題目大意：
有n個加油站分布在 環(huán)形路線上唤崭。其中每個加油站的儲油量為 gas[i]嫁蛇。 你有一輛巨大油箱(可以無限加油)的汽車,從 站點i到下一站i+1您访，油耗為 cost[i]。一開始的時候，汽車油箱是空的伞剑。
如果你能一次開完全程的話，請返回一個起始站點市埋。否則返回-1表示無法完成黎泣。
提示： 測試用例保證答案是唯一的恕刘。
疑問：題目未明顯指出 是順時針開或逆時針開。但從測試數(shù)據(jù)理解 站點i 到 站點i+1抒倚，應該是順時針開的褐着。
解題思路：
首先可以明確的是，如果 總油耗sum{cost[0...n]} 大于 總儲量sum{gas[0...n]}的話托呕，是無法完成任務的含蓉。直接返回-1。
接著项郊，思考一下當 總油耗 小等于 總儲量時馅扣，是否必然存在可行解。
C(i) + C(i+1) + C(i+2) + C(i+3) ... + C(i+n) = C
G(i) + G(i+1) + G(i+2) + G(i+3) ... + G(i+n) = G
G >= C
如果 平均分布的話着降， 則 G(i)>=C(i) 差油。 必然是ok的。
考慮極限情況任洞，C(i) 油耗巨大蓄喇。貪心策略保證每站必停(油不加白不加)，我們從i站點逆時針選點侈咕」保基于貪心考慮，逆時針選站點要保證對經(jīng)過C(i)最大油耗是有利：每一次后退選點對總油耗是正向的耀销。
枚舉 (Time Limit Exceeded)
時間復雜度 大致為 O(n^2)楼眷。 測試用例數(shù)據(jù)極為暴力。熊尉。
int goRound(int starInx,int *gas,int gasSize,int *cost,int costSize){
int nowGas = 0;
int nowIdx = starInx;
for(int i=0;i<gasSize;i++){
nowGas += gas[nowIdx];
if(nowGas < cost[nowIdx]) return -1;
nowGas -= cost[nowIdx];
nowIdx = (nowIdx+1)%gasSize;
}
return nowGas >= 0 ? starInx : -1;
}
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
int ans = -1;
int totalGas = 0, totalCosts = 0;
for(int i=0;i<costSize;i++){
totalCosts += cost[i];
}
for(int i=0;i<gasSize;i++){
totalGas += gas[i];
}
if(totalGas < totalCosts) return ans;
for(int i=0;i<gasSize;i++){
if((ans = goRound(i,gas,gasSize,cost,costSize)) != -1){
break;
}
}
return ans;
}
貪心 (Accepted)
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
int totalGas = 0, totalCosts = 0;
int maxCostIdx = -1, maxCost = -1;
for(int i=0;i<costSize;i++){
totalCosts += cost[i];
if(cost[i] > maxCost){
maxCostIdx = i;
maxCost = cost[i];
}
}
for(int i=0;i<gasSize;i++){
totalGas += gas[i];
}
if(totalGas < totalCosts) return -1;
int tmp = maxCostIdx;
int tmpMaxgas = gas[tmp];
int tmpMaxCost = cost[tmp];
while (tmpMaxgas < tmpMaxCost || gas[tmp] >= cost[tmp]) { // 貪心策略
tmp--;
if(tmp == -1) tmp = gasSize - 1;
if(tmp == maxCostIdx) break;
tmpMaxgas += gas[tmp];
tmpMaxCost += cost[tmp];
}
return (tmp+1)%gasSize;
}
Accepted
