Gas Station

Gas Station
- Description
- Example
- Analysis
  - AC Picture
  - Code
- Further
  - AC Picture
  - Code

Description

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 in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.

Example

Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

Analysis

题目的意思是，给定一个环状数组，每个节点代表一个城市，城市内有 g[i] 的汽油可以补充，从城市 i 到城市 i+1 需要耗费 c[i] 的汽油。
假设我们开着一个拥有无限容量的车，顺时针经过所有城市。起始城市可以自己决定，现要求输出能否完成一次回到起点的旅行。
注意，题目保证输入的 g[1…n] 和 c[1…n] 拥有相同长度且元素非负。如果有解，那么解唯一。

基于解唯一，我们立刻可以想到一个带剪枝的 $O(n^2)$ 枚举算法，首先找到第一个可以出发的地点，然后从这里开始往后遍历，查找是否存在可以完成旅行的点：

# 查找第一个起始点
start = 0
for i from 1 to n:
  if (g[i]-c[i]>0):
    start = i
    break

# 开始遍历，查找解
for i from start to n:
  tank = 0
  flag = True
  # 去除无法开始的点
  if (g[i]-c[i]>=0):
    index = start
    for j from 1 to n:
      tank += g[index%n] - c[index%n]
      if tank < 0:
        flag = False
        break
      index += 1
  else:
    flag = False
  # 解唯一，找到退出
  if flag:
    return start
  start += 1
return -1

AC Picture

Code

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int size = gas.size(), start = 0, tank = 0;
    bool flag = true;
    for (int i = 0; i < size; ++i) {
      if (gas[i]-cost[i]>=0) {
        start = i;
        break;
      }
    }

    for (int i = start; i < size; ++i) {
      tank = 0;
      flag = true;
      if (gas[i] - cost[i] >= 0) {
        for (int cnt = 0, j = i; cnt < size; ++cnt, ++j) {
          tank += gas[j % size] - cost[j % size];
          if (tank < 0) {
            flag = false;
            break;
          }
        }
      } else {
        flag = false;
      }
      if(flag)  return i;
    }
    return -1;
  }

Further

枚举的速度实在是太慢了，我们再来考虑一下题目：

对于 g[1…n] 和 c[1…n]，如果 $\sum_{i=1}^{n}{g[i]} \lt \sum_{i=1}^{n}{c[i]}$，那么必然是不可达的，因为储存汽油不足以支持完成旅行的开销
对于城市 i 和 j(i < j)，如果 i 到 j 不可达，那么 $\forall k \in {k | i < k < j}$，k 到 j 亦不可达。这是很好理解的，从 i 出发，在到达城市 j 前的任一个城市 k 时，我们要么富余汽油，要么用光。所以，从 i 出发到 k 时，tank >= 0，设富余量为 res。如果 i 到 j 不可达，那么，res + result[k, j] < 0。这必然可以推出 result[k, j] < 0，也就是 k 到 j 不可达。

第一条性质，可以预先判断是否有解。第二条性质，可以帮助构造 $O(n)$ 的寻解算法：

start = 0
for i from 1 to n:
  if tank += g[i] - c[i] < 0:
    start = i + 1
    tank = 0
return start

AC Picture

AC2

Code

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  int size = gas.size(), start = 0, tank = 0, total = 0;
  for (int i = 0; i < size; ++i) {
    tank += gas[i] - cost[i];
    if (tank < 0) {
      start = i + 1;
      total += tank;
      tank = 0;
    }
  }
  
  return total + tank < 0 ? -1 : start;
}