GasStation.cc

#include "leet.h"




#include <algorithm>
#include <cstring>

class Solution{
  public:
    int canCompleteCircuit(vector<int>& gas, vector<int> &cost){
        int len = gas.size();
        for (int i = 0; i < len; ++i){
            gas[i] -= cost[i];
        }

        int sum = 0;
        for (int i = 0, j = 1; i < len; i += j){
            sum = 0;
            for (j = 1; j <= len; ++j){
                auto p = (i + j - 1) % len;
                sum += gas[p];
                if (sum < 0){
                    break;
                }
            }
            if (j > len){
                return i;
            }
        }
        return -1;
    }
};



int main(){
    Solution slu;
    vector<int> g = {67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66};
     vector<int> c ={27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};

    //g = {1,2,3,3};
    //c = {2,1,5,1};
    g = {1,3};
    c = {2,1};

    cout << slu.canCompleteCircuit(g, c) << endl;


    return 0;
}