Advertisement
mickypinata

LEET-T0134: Gas Station

Nov 18th, 2021
563
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> gas, cost;
  5.  
  6. int canCompleteCircuit(vector<int> &gas, vector<int> &cost){
  7.     int n = gas.size();
  8.     int sumGas = 0;
  9.     int sumCost = 0;
  10.     int cur = 0;
  11.     int mn = 0;
  12.     int ans = 0;
  13.     for(int i = 0; i < n; ++i){
  14.         sumGas += gas[i];
  15.         sumCost += cost[i];
  16.         cur += gas[i] - cost[i];
  17.         if(cur < mn){
  18.             mn = cur;
  19.             ans = (i + 1) % n;
  20.         }
  21.     }
  22.     if(sumGas < sumCost){
  23.         return -1;
  24.     }
  25.     return ans;
  26. }
  27.  
  28. int main(){
  29.  
  30.     int n;
  31.     scanf("%d", &n);
  32.     for(int i = 1; i <= n; ++i){
  33.         int x;
  34.         scanf("%d", &x);
  35.         gas.push_back(x);
  36.     }
  37.     for(int i = 1; i <= n; ++i){
  38.         int x;
  39.         scanf("%d", &x);
  40.         cost.push_back(x);
  41.     }
  42.     cout << canCompleteCircuit(gas, cost);
  43.  
  44.     return 0;
  45. }
  46.  
Advertisement
RAW Paste Data Copied
Advertisement