134. Gas Station

LeetCode - 134.Gas Station

题目大意：

有n个加油站分布在 环形路线上。其中每个加油站的储油量为 gas[i]。 你有一辆巨大油箱(可以无限加油)的汽车,从 站点i到下一站i+1，油耗为 cost[i]。一开始的时候，汽车油箱是空的。

如果你能一次开完全程的话，请返回一个起始站点。否则返回-1表示无法完成。

• 提示： 测试用例保证答案是唯一的。

• 疑问：题目未明显指出 是顺时针开或逆时针开。但从测试数据理解 站点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站点逆时针选点。基于贪心考虑，逆时针选站点要保证对经过C(i)最大油耗是有利：每一次后退选点对总油耗是正向的。

枚举 (Time Limit Exceeded)

时间复杂度 大致为 O(n^2)。 测试用例数据极为暴力。。

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